【LeetCode每日打卡】面试题56 - I. 数组中数字出现的次数

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

示例 1：

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

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

限制：

2 <= nums <= 10000

已经一整个月没做过一道算法题了

这道题乍一看 我也不会，但是看了答案恍然大悟（悟出来 明明看过原题却忘了，自己还是技术不行啊）

分析

1. 先从所有数里面只有一个数出现一次算，解答方案 很经典就是 全员异或，出现两次 异或为0，单独的一个就留下来了。
2. 题目升级变成两个之后，如果还按之前的方法，全员异或，得到的结果是 出现一次的两个数 的异或结果。
3. 两个数异或的结果 在二进制下为1的那一位肯定 不相同。
4. 举个栗子

数 二进制

1 0001

1 0001 2 0010 3 0011 3 0011 4 0100 4 0100 5 0101 5 0101 6 0110 6 0110 7 0111 8 1000 8 1000 9 1001 9 1001 异或 结果 0010异或1111 为 1101

可以看出 两个数 最低位是 不同的，就可以把全部数字 分成两部分

1 0001 1 0001 3 0011 3 0011 5 0101 5 0101 7 0111 9 1001 9 1001

2 0010 6 0110 6 0110 4 0100 4 0100 8 1000 8 1000

两部分再分别走 最基础的全员异或 得到的救过就是 两个只出现一次 的数

c++题解

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ret = 0;
        for (int n : nums)
            ret ^= n;
        int div = 1;
        while ((div & ret) == 0)
            div <<= 1;
        int a = 0, b = 0;
        for (int n : nums)
            if (div & n)
                a ^= n;
            else
                b ^= n;
        return vector<int>{a, b};
    }
};