如何使空间复杂度为O(1)

Question

我试图回答以下问题:你有一个整数数组,这样每个整数都有一个奇数个时间,除了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)空间做更好的方法吗？

谢谢.

Answer 1

我以稍微不同的方式使用 Lashane 的提议来尝试回答：

字符 negBits[268435456]; // 2 ^ 28 = 2 ^ 30（负整数的数量）/ 8（字符的大小）
字符 posBits[268435456]；// 同上，除了正数

int 数字[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };

for (int num : number){
   如果（数字 < 0）{
       num = -(num + 1);// 如果没有这个 + 1，Integer.MIN_VALUE 将被排除
       negBits[ << 4] ^= ((num & 0xf) >> 1);
   }
   别的 {
       posBits[num << 4] ^= ((num & 0xf) >> 1);
       // 获取要混乱的仪式字符
       // 切换位来表示整数值。
   }
}

// 现在是困难的部分，找到所有切换后的值：

for (int i = 0; i < Integer.MAX_VALUE; i++){
    if (negBits[i << 4] & ((i & 0xf) >> 1)){
        System.out.print(" " + (-i - 1));
    }
    if (posBits[i << 4] & ((i & 0xf) >> 1)){
        System.out.print(" " + i);
    }
}

根据评论中的讨论，此答案值得注意以下几点：

• 假设 Java 为 32 位。
• Java 数组有 Integer.MAX_INT 的固有限制