如何使空间复杂度为O(1)
如何使空间复杂度为O(1)
提问于 2016-01-16 03:56:28
我试图回答下面的问题:你有一个整数数组，使得每个整数出现奇数次，除了其中的3个。找到这三个数字。
到目前为止，我使用的是蛮力方法：
public static void main(String[] args) {
// TODO Auto-generated method stub
int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };
FindEvenOccurance findEven = new FindEvenOccurance();
findEven.getEvenDuplicates(number);
}
// Brute force
private void getEvenDuplicates(int[] number) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i : number) {
if (map.containsKey(i)) {
// a XOR a XOR a ---- - -- - - odd times = a
// a XOR a ---- -- -- --- - even times = 0
int value = map.get(i) ^ i;
map.put(i,value);
} else {
map.put(i, i);
}
}
for (Entry<Integer, Integer> entry : map.entrySet()) {
if (entry.getValue() == 0) {
System.out.println(entry.getKey());
}
}
}它工作得很好，但效率不高。
o/p：
1
5
6
8但问题指出，我们需要在O(1)空间和O(N)时间复杂度内完成这项工作。对于我的解决方案，时间复杂度是O(N)，但空间复杂度也是O(N)。有人能建议我用O(1)空间做这件事的更好的方法吗？
谢谢。
回答 2
Stack Overflow用户
发布于 2016-01-27 04:23:08
不幸的是，如果我们使用严格的空间感，即O(1)空间被输入阵列中使用的最大空间所约束，则不可能获得O(1)空间和O(n)复杂度的解。
在弱空间意义下，一个任意的大整数仍然适合O(1)，您可以只将计数器编码为这一个整数的位。从所有位设置为1开始。当您在输入数组中遇到数字n时，切换第n位。最后剩下的所有位都表示偶数次遇到的3个数字。
Stack Overflow用户
发布于 2016-01-27 03:06:35
你对问题的概述和例子不匹配。你说你在你的问题中寻找3个整数，但是这个例子显示了4。
我不确定如果没有额外的限制，这是不可能的。在我看来，最坏的情况下，长度复杂度将始终至少是O(N-6) => O(N)，没有排序列表，并且具有完整的整数集。
如果我们从排序数组开始，那么是的，很简单，但是这个约束没有指定。自己对数组进行排序将会在时间或空间上过于复杂。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34818865
复制相关文章
相似问题
腾讯云开发者
