重新排列列表中的项目，以使相邻的两个项目都不相同 [英] Rearrange items in a list such that no two adjacent are same

问题描述

我们如何最有效地做到这一点?给定一个包含重复项目的列表，任务是重新排列列表中的项目，以使两个相邻项目都不相同.

 输入:[1,1,1,2,3]输出:[1,2,1,3,1]输入:[1,1,1,2,2]输出:[1,2,1,2,1]输入:[1,1]输出:不可能输入:[1,1,1,1,2,3]输出:不可能 

通用算法也很好！不需要是Python.

解决方案

我不擅长python，所以我在这里编写通用算法-

1. 建立最大堆， maxHeap ，用于存储数字及其频率< array元素，frequency> . maxHeap 将根据元素的频率进行排序.

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

p>

3. maxHeap 不为空

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

4. 如果结果数组的长度和原始数组的长度相同，则此数组没有解决方案.否则返回结果数组.

编辑

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

How can we do it most efficiently? Given a list with repeated items, task is to rearrange items in a list so that no two adjacent items are same.

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

Edit: General Algorithm is fine too! It doesn't need to be Python.

解决方案

I am not good at python, so I am writing the general algorithm here -

1. Build a max heap, maxHeap that stores numbers and their frequencies <array element, frequency>. maxHeap will be sorted based on the frequency of element.

2. Create a temporary Key that will used as the previous visited element ( previous element in resultant array. Initialize it as <item = -inf , freq = -1>.

3. While maxHeap is not empty

   • Pop an element and add it to result.
   • Decrease frequency of the popped element by 1
   • Push the previous element back into the max heap if it's frequency > 0
   • Make the current element as previous element for the next iteration.

4. If length of resultant array and original, there is no solution for this array. Else return the resultant array.

Edit

Those who're wondering why the greedy solution by putting the current most frequent element in even/odd positions by skipping one position each time won't work, you can try with the test-case [1 1 2 2 3 3].

这篇关于重新排列列表中的项目，以使相邻的两个项目都不相同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！