LeetCode260 只出现一次的数字III

发表于 | 分类于 |
字数统计: 371 | 阅读时长 ≈ 1

链接： https://leetcode-cn.com/problems/single-number-iii/

题面

给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

解法

出现一个的解法已经人尽皆知了，异或所有的数最后的结果就是只出现了一次的数
那么怎么做两个数的情况呢
需要用到分治（严格说来只是分组）的做法
即把两个数通过某种方式分开
首先将所有数异或得到一个结果，得到这个数的最低位是1的位 这一位一定是两个数不同的位
然后通过与运算区分成两组，再通过异或就可以得到最终的结果了

至于如何得到最低位是1的位，有两种方式，一个是循环判断一下找出最低位
还有一种比较快的方式是位运算，通过x & (-x) 可以直接得到最低位（考虑补码的计算方式）

代码

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
26
27
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        vector<int> res(2);
        unsigned mask = 0;
        for (int id: nums) {
            mask ^= id;
        }
        // 笨办法
        int div = 1;
        while((div & mask) == 0) {
            div <<= 1;
        }
        // 位运算
        mask = mask & (-mask);
        for (int id: nums) {
            if (id & div) {
                res[0] ^= id;
            }
            else {
                res[1] ^= id;
            }
        }
        return res;

    }
};