圆形阵列中的间距元素

Question

这是我遇到的一个有趣的问题,我觉得应该有一个优雅,可证明的解决方案,但我还没有完全得到它.我把它定义为:

定义一个函数,该函数将N个元素和一个正整数R的数组作为输入,并返回一个圆形数组(或您视为圆形的数组),其中没有两个相同的元素小于R,或者如果没有这样的则返回null订购是可能的.

所以f([a,b,d,c,a,d,k,a,d], 3)可能会回来[a,b,d,a,k,d,a,c,d],但f([a,b,d,c,a,d,k,a,d,a,a], 3)会回来null.我定义两个元件为R apart如果它们具有R-1在它们之间的元件,所以该阵列中[x,a,b,y],x和y3个分开在一侧上与0相距为另一方.

我觉得这也是一个很棒的面试问题.

Answer 1

1. 将数组拆分为相同元素的组（通过排序或使用哈希表）。
2. 找到最大的一组。如果其大小大于floor(N/R)，则返回 null。
3. 如果最大组的大小恰好等于N/R，则对组列表进行分区（部分排序），以便所有大小相同的组N/R在下一步中排在第一位。
4. 对于每个组，将其元素放入结果数组（循环缓冲区）中，R在可能的情况下将索引递增 。如果R和N不是互质的，有时 - 在N/GCD(N,R)增量之后 - 索引将指向已使用的元素。在这种情况下，增加索引而R+1不是并R继续。