问在数组中分散重复

EN

在perl中

@a=(9,9,9,2,2,2,1,1,1);

然后对列表中不同数字的计数做一个哈希表，就像频率表一样。

map { $x{$_}++ } @a;

然后按已知顺序重复遍历所有找到的键，并将适当数量的单个数字添加到输出列表中，直到所有键都用完为止。

@r=();
$g=1; 
while( $g == 1 ) { 
   $g=0;
   for my $n (sort keys %x) 
      {
      if ($x{$n}>1) {
                    push @r, $n;
                    $x{$n}--;
                    $g=1
                    }
      } 
}

我确信这可以适用于任何支持哈希表的编程语言

沃斯普隆和HugoRune建议的算法的python代码：

from collections import Counter, defaultdict

def max_spread(data):
    cnt = Counter()
    for i in data: cnt[i] += 1

    res, num  = [], list(cnt)
    while len(cnt) > 0:
        for i in num:
            if num[i] > 0:
                res.append(i)
                cnt[i] -= 1
            if cnt[i] == 0: del cnt[i]

    return res

def calc_spread(data):
    d = defaultdict()
    for i, v in enumerate(data):
        d.setdefault(v, []).append(i)

    return sum([max(x) - min(x) for _, x in d.items()])

HugoRune's answer利用了不寻常的评分函数，但实际上我们可以做得更好:假设有d个不同的非唯一值，那么一个最优解唯一需要的是，输出中的第一个d值必须以任何顺序由这些值组成，同样，输出中的最后d值必须以任意(可能是不同的)顺序包含这些值。(这意味着所有唯一数字都出现在每个非唯一数字的第一个和最后一个实例之间。)

非唯一数字的第一次拷贝的相对顺序并不重要，同样的，它们的最后一次拷贝的相对顺序也不重要。假设值1和2在输入中都出现多次，并且我们已经按照我在第一段中给出的条件建立了一个候选解，第一次拷贝在i位置，第一份拷贝在第1位，第一份拷贝在第j>i位置。现在假设我们交换这两个元素。元素1被推到右边的j- i位置，所以它的分数贡献会下降j- i，但是元素2被推到了j-i位置，所以它的分数贡献会增加j-i，这些抵消，保持总得分不变。

现在，任何元素的排列都可以通过以下方式交换元素:将位置1中的元素与应该位于位置1的元素交换，然后对位置2执行同样的操作，依此类推。在第一步之后，排列的第一I元素是正确的。我们知道，每个交换都保持评分函数不变，而置换只是交换序列，所以每个置换也使得分函数保持不变！对于输出数组两端的d元素，这是正确的。

当存在一个数字的3个或多个副本时，只有第一个和最后一个副本的位置才能影响该数字的距离。中间的元素在哪里并不重要，，我将在d元素的两个块之间调用“中心”元素。它们包括唯一的元素，以及至少3次出现的所有非唯一元素的一些副本。和以前一样，很容易看到这些“中心”元素的任何排列都对应于一个交换序列，并且任何这样的交换都将保持总得分不变(事实上，它甚至比以前更简单，因为交换两个中心元素甚至不会改变这些元素中任何一个的得分贡献)。

这导致了一个简单的O(nlog n)算法(如果第一步使用桶排序)来从长度-n个输入数组X生成一个解决方案数组Y：

1. 对输入数组X进行排序。
2. 使用一次遍历X来计数不同的非唯一元素的数量。打电话给d。
3. 将i，j和k设为0。
4. 而我< n：
   • 如果Xi+1 == Xi，我们有一个非唯一的元素：。
     • 设Yj = Yn-j-1 = Xi。
     • 增量i两次，增量j一次。
     • 而Xi == Xi-1：
       • 设置Yd+k = Xi。
       • 增量I和k。

​

​

- Otherwise we have a unique element:  
    - Set Y[d+k] = X[i].
    - Increment i and k.

​

​