剑指 Offer 56 - I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

示例 1：

输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

思路：直接参考题解

假设只出现一次的两个数分别为x和y

  1. 首先将数组中所有数进行异或，因为两个相同的数异或后为0，因此最终的结果就是x和y的异或值
  2. 我们找到第一步结果中二进制的一个1位，该位的值为1，说明x和y在该位的值不同
  3. 我们循环数组，将数组进行分组，将x和y分在不同组。分组的标准就是第二步中的那一位1。将组内的数进行异或，因为只有x和y出现一次，因此两组异或的结果分别就是所求的x和y。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int[] singleNumbers(int[] nums) {
        int x = 0;
        int y = 0;
        int n = 0;
        int m = 1;
        // 求 x ^ y 的值
        for (int num : nums) {
            n ^= num;
        }
        // 找到x ^ y的二进制值中的1位，这一位表示x和y在该位上值不同，用于分组
        while ((n & m) == 0) {
            m <<= 1;
        }
        // 遍历nums进行分组，x和y被分在不同组，那么两组异或的结果就是所求的x和y
        for (int num : nums) {
            if ((num & m) != 0) {
                x ^= num;
            } else {
                y ^= num;
            }
        }
        return new int[]{x, y};
    }
}