重新排列列表中的项目，使得没有两个相邻项目是相同的[重复]

我们怎样才能最有效地做到这一点？ 给定一个包含重复项目的列表，任务是重新排列列表中的项目，以便没有两个相邻项目是相同的。

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，所以我在这里写通用算法 -

1. 构建最大堆 https://stackoverflow.com/questions/2501457/what-do-i-use-for-a-max-heap-implementation-in-python, maxHeap存储数字及其频率<array element, frequency>. maxHeap将根据元素出现的频率进行排序。

2. 创建一个临时键，用作前一个访问过的元素（结果数组中的前一个元素。将其初始化为<item = -inf , freq = -1>.

3. While maxHeap不为空

   • 弹出一个元素并将其添加到结果中。
   • 弹出元素的频率减少 1
   • 如果前一个元素的频率 > 0，则将其推回最大堆
   • 使当前元素作为下一次迭代的前一个元素。

4. 如果结果数组的长度与原始数组的长度相同，则该数组无解。否则返回结果数组。

Edit

那些想知道为什么通过每次跳过一个位置将当前最频繁的元素放在偶数/奇数位置的贪婪解决方案不起作用的人，您可以尝试使用测试用例[1 1 2 2 3 3].