面试题56 - I. 数组中数字出现的次数

题目描述

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

---数组中数字出现的次数

示例：

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

输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

---

提示：
2 <= nums <= 10000

转载来源：力扣（LeetCode）

---

题目分析

这是这一系列题的最后一道，也是做法很巧的一道，它的简单版是：“数组里只有一个数字出现了一遍，其他数字都出现了两遍”，解法是将数组里的所有数字都异或起来，结果就是那个出现了一次的数字，原理是“两个相同的数异或的结果是零”，这道题也可以用相似的做法，将所有数异或起来，结果就是两个不相同的数的异或的结果；

得到两个目标数异或的结果，这有什么用呢？从下面的图我们可以发现，两个数按位异或的结果的二进制表示里为1的，其实就是两个数不相同的位，利用这个不相同的位，我们就可以区分这两个数了！

异或

同样的，我们可以利用这个不相同的位，将数组分成两部分，一部分是这个位为0的，一部分是这个位为1的，而答案的那两个数自然就被分开了（其他被分开的数都是成对被分开的），这两组数都可以用简易版题的方法得到只出现一次的数，这两个数组合起来就是这题的答案了！

public int[] singleNumbers(int[] nums) {
        int ans = 0;
        for (int num : nums)
            ans ^= num;
        int pos = 1;
        while ((ans & pos) == 0) { 
            pos <<= 1;
        }
        int a = 0, b = 0;
        for (int num : nums) {
            if((num&pos) == 0)
                a ^=  num;
            else
                b ^= num;
        }
        return new int[]{a,b};
    }

代码文件

---

最快的也是用位运算，误差范围内