来源：Google 面试题
编写一段代码，确保输入中相同的元素在输出中尽可能地扩散？
基本上，我们需要以这样的方式放置相同的元素，使得总体扩散最大化。
例如：
Input: {1,1,2,3,2,3}
Possible Output: {1,2,3,1,2,3}
Total dispersion = Difference between position of 1's + 2's + 3's = 4-1 + 5-2 + 6-3 = 9 .
我不确定是否有针对这个问题的最优多项式时间算法。除此之外，没有提供任何其他细节。
我的想法是计算输入中每个元素的频率，然后将它们按顺序排列在输出中，每次一个不同的元素，直到所有频率都用完为止。
我不确定我的方法是否可行。
有什么其他方法/想法吗？
{1, 1, 1, 1, 2, 3, 4} ==> {1, 2, 3, 4, 1, 1, 1}{1, 1, 1, 2, 2, 2, 3, 4} ==> {1, 2, 3, 4, 1, 2, 1, 2}
然而，我认为这是根据提供的评分函数得到的最佳分布。
由于离散度分数计算距离之和而不是距离平方和，因此您可以有几个相邻的重复项，只要您在其他地方有一个大的间隔来补偿。1,1,1,1,2,2,2,2,3，这将输出 1,2,3,1,2,1,2,1,2（对吗？），但我认为 1,2,1,2,3,1,2,1,2 更好。 - Bernhard Barker@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
}
}
}
根据Vorsprung和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的答案利用了不寻常的评分函数，但我们实际上可以做得更好：假设有d个不同的非唯一值，则解决方案要想达到最优，唯一需要的是输出中的前d个值必须包含这些值的任意组合，同样地，输出中的最后d个值必须包含这些值的任意（即可能是不同的）组合。（这意味着所有唯一数字都出现在每个非唯一数字的第一个和最后一个实例之间。）
非唯一数字的第一个副本的相对顺序不重要，同样最后一个副本的相对顺序也不重要。 假设值1和2在输入中都出现了多次，并且我们已经建立了一个符合我在第一段给出的条件的候选解，其中1的第一个副本在位置i处，而2的第一个副本在位置j>i处。现在假设我们交换这两个元素。元素1已经向右移动了j-i个位置，因此它的分数贡献将下降j-i。但是元素2已经向左移动了j-i个位置，因此它的分数贡献将增加j-i。这些会相互抵消，从而总分数不变。现在，可以通过以下方式交换元素来实现任何元素的排列：将在位置1的元素与应在位置1的元素交换，然后对于位置2进行相同的操作，依此类推。在第i步之后，排列的前i个元素是正确的。我们知道每次交换都不会改变评分函数，而置换只是交换序列，因此每个置换也都不会改变评分函数！这适用于输出数组两端的d个元素。
当一个数字存在3个或更多的副本时，只有第一个和最后一个副本的位置对该数字的距离有贡献。中间的副本放在哪里并不重要。我将在两个端点的d个元素块之间的元素称为“中央”元素。它们由唯一的元素组成，以及出现至少3次的所有非唯一元素的若干个副本。与之前一样，很容易看出这些“中央”元素的任何排列都对应于一系列交换，并且任何这样的交换都不会改变总分数（实际上比之前更简单，因为交换两个中央元素甚至不会改变这些元素的得分贡献）。
这导致了一个简单的O(nlog n)算法（如果您在第一步使用桶排序，则为O(n)）来从长度为n的输入数组X生成解决方案数组Y：