所以我正在尝试解决以下面试问题:
/** Given an unordered array of positive integers, create an algorithm that makes sure
no group of integers of size bigger than M have the same integers.
Input: 2,1,1,1,3,4,4,4,5 M = 2
Output: 2,1,1,3,1,4,4,5,4
*/
我想到了一个复杂度为 O(n^2) 的解决方案:遍历数组并交换给定组中重复的相邻项。但是因为你有像 1,2,3,4,1,1 M = 2 这样的情况,你可能必须在数组的后面环绕 n 次,给你多项式时间。
所以我想到了以下解决方案,它应该在线性时间内运行:
public static int[] regroup(int[] input, int m) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i : input) {
if (!map.containsKey(i)) {
map.put(i, 1);
} else {
map.put(i, map.get(i) + 1);
}
}
int i = 0, n = 0;
while (i < input.length) {
for (int curr : map.keySet()) {
if (n == m) {
n = 0;
break;
}
if (map.get(curr) > 0) {
input[i] = curr;
map.put(curr, map.get(curr) - 1);
i++; n++;
} else {
continue;
}
}
}
return input;
}
这实质上是将所有值都设为它们的出现次数的 hashmap,然后从每个桶中为每个 M 大小的组选择一个项目,保证唯一的项目。虽然我遇到的问题是下面的反例:
{2,1,1,1,3,4,4,4,5} M = 3
返回
[1, 2, 3, 1, 4, 5, 1, 4, 4]
这显然是不对的。发生的事情是最后没有独特的元素可供选择,所以只需将 4 两次放入最后一组。谁能想出一种方法来解决这个问题并保持线性时间?
最佳答案
一旦你对所有元素进行了计数,然后将它们放入堆中(数字,计数)。 从堆中取出一对并开始将它们分配到输入数组中,差异为 M,直到到达输入数组的末尾。一旦你到达数组的末尾,然后从数组的前一个开始的下一个位置开始。代码片段如下:
int curr = 0;
int start = curr;
while(maxHeap.size() > 0){
Pair p = maxHeap.poll();
int i =0;
while(i < p.count){
input[start] = p.num;
// keep putting element at gap of m
start = start + m;
// if exceeded the length of input array , wrap around with previous start +1.
if(start >= input.length){
curr++;
start = current;
}
i++;
}
}
return true;
}
关于arrays - 重新排序数组 s.t.组中没有重复项,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21413501/