您好,我正在寻找一种算法,如果给定一个数组作为输入,它将重新排列它,以便尽可能减少相等相邻值的数量。
我会试着解释一下:
in:[4,4,4,4,5,5,5,5] -> out: [4,5,4,5,4,5,4,5] or [5,4,5,4,5,4,5,4]
in:[1,2,3,4,5,6,7,8] -> out:
任何顺序都可以,因为所有值都不同
输入:[1,1,2,2,3,3,1,1] -> 输出:[1,2,1,3,1,2,3,1]
或相邻值不相等的任何其他组合
谢谢!
最佳答案
假设 max_cnt
是所有元素中出现的最大次数,n
是数组的大小。
如果没有元素出现超过 ceil(n/2)
次,则可以使所有相邻元素不同,因为可以按照元素之间的距离来排列它们具有相同值的至少为 2。示例:
一 = [1, 1, 1, 1, 2, 2, 3]。我们可以这样重新排列它:[1, 2, 1, 2, 1, 3, 1]。
重新排列的算法很简单:将相等的元素放在位置 i, i + 2, i + 4, ...
等等。
如果 max_cnt > ceil(n/2)
个位置,那么您可以使用上述算法构造没有相等相邻元素的最长可能前缀,然后用剩余值填充后缀。例子:
一 = [1, 1, 1, 1, 2, 3]。前缀是 [1, 2, 1, 3, 1]。剩下的用剩下的填充:[1, 2, 1, 3, 1, 1, 1]。相等的相邻元素数为 2 * max_cnt - n - 1
。
关于arrays - 具有最小数量的相等相邻值的数组改组,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26561419/