数组中只出现一次的两个数 -- 剑指 Offer

数组中只出现一次的两个数 -- 剑指 Offer

Administrator 429 2020-11-10

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例

输入：[1,2,3,3,4,4]

输出：[1,2]

思路及证明过程

1、暴力枚举 + 模拟 Map

  • 时间复杂度 - $O(N)$
  • 空间复杂度 - $O(N)$

最简单的想法，枚举每个数，并将其加入 Map ，再次遇到就 increase

2、按位划分

  • 时间复杂度 - $O(N)$
  • 空间复杂度 - $O(1)$

原理：当一个数组中只有一个元素只出现一次时，由于相同元素异或操作为 0 ，故只需要一次异或遍历就可以得出只出现过一次的值

在本题中，依旧可以使用这种方法。

  1. 先异或枚举所有的值，最后得到值 $C = A \oplus B$
  2. 因为 $A\not= B$ ，故必然有 $A \oplus B \not= 0$
  3. 则可取 $C$ 中的一个 $1$ 位，用该位将原区间划分成两个不同的区间
  4. 由于原区间中除 $A$ , $B$ 外，其余的数都出现了两次，故此时就变成了两个区间中，各有一个元素只出现过一次
  5. 再次异或遍历即可

Code

暴力枚举

class Solution {
  private static final int N = 1010;
  private static final int[] q = new int[N];
  
  public int[] findNumsAppearOnce(int[] nums) {
    for (int i : nums) q[i]++;
    int[] ret = new int[2];
    for (int i = 0, j = 0; i < 2; i++) {
      while (j < nums.length && q[nums[j]] > 1) j++;
      ret[i] = nums[j];
    }
    
    return ret;
  }
}

按位划分

class Solution {
  public int[] findNumsAppearOnce(int[] nums) {
    int tar = 0;
    for (int i : nums) tar ^= i;
    
    int bit = 0;
    while ((tar >> bit & 1) == 0) bit++;
    
    int first = 0;
    for (var i : nums) 
      if ((i >> bit & 1) != 0) 
        first ^= i;
    
    return new int[] { first, tar ^ first };
  }
}
Algorithm