arrays - 具有最小数量的相等相邻值的数组改组

Question

您好，我正在寻找一种算法，如果给定一个数组作为输入，它将重新排列它，以便尽可能减少相等相邻值的数量。

我会试着解释一下:

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]或相邻值不相等的任何其他组合

谢谢!

Answer 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。