Google电面题，List中的duplicate最小距离

csgtc 发表于 2014-3-12 23:02
loop一遍数duplicates, 比如C重复3次，B重复2次，A重复1次， 那么要让所有duplicates的distance尽可能大，必 ...

complexity是O(N)

RomanC 发表于 2014-3-12 22:51
比如[A,A,A,A,B,B,C]，最小距离为2，合法的应该是[A,B,A,B,A,C,A]，感觉构造的方法没有我说的那么简单。。 ...

你这个case显然可以， 频率最多的A隔2个位置能放满， 然后放B, 然后C

csgtc 发表于 2014-3-12 23:02
loop一遍数duplicates, 比如C重复3次，B重复2次，A重复1次， 那么要让所有duplicates的distance尽可能大，必 ...

对， 是这个意思， 但感觉没法证明。

应该 greedy 能 work 啊。Count frequency，然后用 min distance 来 assign positions. 注意这里应该先 assign frequency 最多的那个duplicate，因为他们的 bound 最 tight，必须先满足。所以涉及到 sorting，那么应该是 O(n log n).

证明思路：假设有 solution 但是这个方法找不到，也就是在 assign 某个 duplicate x 时，假设重复k次，之前已经assign了 i-1个，所以这个 dup 会被 assign 到 i, i+d, i+2d, ... i+kd，这个方法 fail 说明 for some j < k, i+jd >= n，也就是不够位置放了。那么唯一解决办法就是把他们整体前移，但问题是之前的元素出现次数 >= k，如果先 assign x 那么必然有其他 dup y 无法满足，所以无解，contradiction.

mark 一下，等会儿看

搞一个hashtable, 存所有字母出现的frequency，然后根据frequency排序。原来的List扔掉。建立新的list，交替插入，先插入frequency最大的一个，然后第二大的一个结点，。。。第一轮插入所有出现的结点，各自frequency减去1. 然后进行新的一轮，直到所有结点的frequency都为0.