1
所以我想通过下面的面试问题的工作:重新排列数组s.t.有一组中没有重复
/** 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放入最后一组。任何人都可以想办法解决这个问题并保持线性时间吗?