我们如何最有效地做到这一点?给定具有重复项目的列表,任务是重新排列列表中的项目,以使两个相邻项目都不相同。
Input: [1,1,1,2,3]
Output: [1,2,1,3,1]
Input: [1,1,1,2,2]
Output: [1,2,1,2,1]
Input: [1,1]
Output: Not Possible
Input: [1,1,1,1,2,3]
Output: Not Possible
编辑:通用算法也很好!不需要是Python。
我不擅长python,因此我在这里编写一般算法-
建立一个最大堆,maxHeap
存储数字及其频率<array element, frequency>
。maxHeap
将根据元素的频率进行排序。
创建一个临时Key,它将用作上一个访问的元素(结果数组中的上一个元素。将其初始化为)<item = -inf , freq = -1>
。
虽然maxHeap
不为空
如果结果数组的长度和原始数组的长度相同,则此数组没有解决方案。否则返回结果数组。
那些想知道为什么通过每次跳过一个位置将当前最频繁的元素置于偶数/奇数位置的贪婪解决方案不起作用的方法,可以尝试一下用例[1 1 2 2 3 3]
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句