在数组中分散重复

Question

来源：谷歌面试问题

编写一个例程，以确保输入中的相同元素在输出中的分布最大？

基本上，我们需要以这样一种方式放置相同的元素，使总传播尽可能最大化。

示例：

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 .

我一点也不确定，是否有一个最佳多项式时间算法可用于此。此外，除此之外，没有为问题提供其他细节。

我的想法是，计算输入中每个元素的频率，然后将它们排列在输出中，每次排列每个不同的元素，直到所有频率都用完。

我不确定我的方法。

任何方法/想法的人。

Answer 1

Vorspring和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()])

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

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

Answer 3

我相信这个简单的算法会奏效：

• 计算每个不同元素的出现次数
• 将多次出现的所有元素的一个实例添加到列表中（每组中的顺序无关紧要）
• 将所有唯一元素的一个实例添加到列表中
• 将多次出现的所有元素的一个实例添加到列表中
• 将出现两次以上的所有元素的一个实例添加到列表中
• 将出现三次以上的所有元素的一个实例添加到列表中

现在，直觉上这不会给出一个好的传播：
对于{1,1,1,2,3,4}==

然而，我认为这是最好的传播，你可以得到的评分函数提供。由于离散度分数计算的是距离之和，而不是距离的平方和，因此，只要在其他地方有较大的差距需要补偿，就可以有多个副本靠近。

对于距离平方和分数，问题变得更加困难。也许面试问题取决于应聘者是否认识到评分函数中的这一弱点？