Single Number III

Question

  1. Given 2*n + 2 numbers, every numbers occurs twice except two, find them.
  3. Example
  4. Given [1,2,2,3,4,4,5,3] return 1 and 5
  6. Challenge
  7. O(n) time, O(1) extra space.

题解

题 Single Number 的 follow up, 不妨设最后两个只出现一次的数分别为 x1, x2. 那么遍历数组时根据两两异或的方法可得最后的结果为 x1 ^ x2, 如果我们要分别求得 x1 和 x2, 我们可以根据 x1 ^ x2 ^ x1 = x2 求得 x2, 同理可得 x_1. 那么问题来了，如何得到x1和x2呢？看起来似乎是个死循环。大多数人一般也就能想到这一步(比如我…)。

这道题的巧妙之处在于利用x1 ^ x2的结果对原数组进行了分组，进而将x1和x2分开了。具体方法则是利用了x1 ^ x2不为0的特性，如果x1 ^ x2不为0，那么x1 ^ x2的结果必然存在某一二进制位不为0（即为1），我们不妨将最低位的1提取出来，由于在这一二进制位上x1和x2必然相异，即x1, x2中相应位一个为0，另一个为1，所以我们可以利用这个最低位的1将x1和x2分开。又由于除了x1和x2之外其他数都是成对出现，故与最低位的1异或时一定会抵消，十分之精妙！

Java

  1. public class Solution {
  2.     /**
  3.      * @param A : An integer array
  4.      * @return : Two integers
  5.      */
  6.     public List<Integer> singleNumberIII(int[] A) {
  7.         ArrayList<Integer> nums = new ArrayList<Integer>();
  8.         if (A == null || A.length == 0) return nums;
  10.         int x1xorx2 = 0;
  11.         for (int i : A) {
  12.             x1xorx2 ^= i;
  13.         }
  15.         // get the last 1 bit of x1xorx2, e.g. 1010 ==> 0010
  16.         int last1Bit = x1xorx2 - (x1xorx2 & (x1xorx2 - 1));
  17.         int single1 = 0, single2 = 0;
  18.         for (int i : A) {
  19.             if ((last1Bit & i) == 0) {
  20.                 single1 ^= i;
  21.             } else {
  22.                 single2 ^= i;
  23.             }
  24.         }
  26.         nums.add(single1);
  27.         nums.add(single2);
  28.         return nums;
  29.     }
  30. }

源码分析

求一个数二进制位1的最低位方法为 x1xorx2 - (x1xorx2 & (x1xorx2 - 1)), 其他位运算的总结可参考 Bit Manipulation。利用last1Bit可将数组的数分为两组，一组是相应位为0，另一组是相应位为1.

复杂度分析

两次遍历数组，时间复杂度 O(n), 使用了部分额外空间，空间复杂度 O(1).

Reference