资料来源：谷歌面试问题
编写一个例程以确保输入中的相同元素最大程度地分布在输出中？
基本上，我们需要以这样的方式放置相同的元素，以使TOTAL传播尽可能最大。
例子：
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 .
我完全不确定，是否有可用的最佳多项式时间算法。此外，除此之外，没有 提供任何其他细节。
我的想法是，计算输入中每个元素的频率，然后将它们排列在输出中，一次每个不同的元素，直到所有频率都用完。
我不确定我的方法。
任何方法/想法的人。
我相信这个简单的算法会起作用：
现在，这在直觉上不会给出很好的传播：
for {1, 1, 1, 1, 2, 3, 4}==> {1, 2, 3, 4, 1, 1, 1}
for {1, 1, 1, 2, 2, 2, 3, 4}==>{1, 2, 3, 4, 1, 2, 1, 2}
但是，我认为这是给定提供的评分功能可以获得的最佳点差。由于分散分数计算的是距离的总和而不是距离的平方和，因此您可以将多个重复项放在一起，只要您在其他地方有很大的差距来补偿。
对于距离平方和得分，问题变得更难。也许面试问题取决于候选人认识到评分功能的这一弱点？
在 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
}
}
}
我确信这可以适应任何支持哈希表的编程语言
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 > 一世。现在假设我们交换这两个元素。元素 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：