分散数组中的重复项

Question

来源:Google面试问题

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

基本上,我们需要以这样的方式放置相同的元素,使得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 .

我不是在所有 肯定的是,如果有可用的this.Also最佳多项式时间算法,没有其他细节提供了除此之外的其他问题.

我的想法是,计算输入中每​​个元素的频率,然后将它们一次排列在输出中,每个不同的元素,直到所有频率都耗尽.

我不确定我的做法.

任何方法/想法的人.

Answer 1

我相信这个简单的算法会起作用：

• 计算每个不同元素出现的次数。
• 制定一个新清单
• 将出现多次的所有元素的一个实例添加到列表中^{_{（每组内的顺序并不重要）}}
• 将所有唯一元素的一个实例添加到列表中
• 将出现多次的所有元素的一个实例添加到列表中
• 将出现两次以上的所有元素的一个实例添加到列表中
• 将出现次数超过三次的所有元素的一个实例添加到列表中
• ...

现在，直观上这不会提供良好的传播：
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}

然而，我认为鉴于提供的评分功能，这是您可以获得的最佳传播。由于分散分数计算距离的总和而不是距离的平方和，因此只要在其他地方有较大的间隙需要补偿，就可以将多个重复项靠近在一起。

对于距离平方和分数，问题变得更难。也许面试问题取决于候选人认识到评分功能的这一弱点？