arrays - 圆形阵列中的间隔元素

Question

这是我遇到的一个有趣的问题，我觉得应该有一个优雅的、可证明的解决方案，但我还没有完全能够得到它。我将其定义为:

Define a function that takes as input an array of N elements and a positive integer R, and returns a circular array (or an array that you treat as circular) where no two identical elements are less than R apart, or a null if no such ordering is possible.

所以 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-1 元素，我将两个元素定义为 R apart，因此在数组 [x,a,b,y]、x 和 y 一侧相距 3，另一侧相距 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 并继续。