QeuroIzoのBlog

hello world

0%

22. 只出现一次的数字 III

发表于

题目

解析

  1. 所有元素只有两个出现一次，其余的出现两次，那么对所有的元素求异或和，那么最后求出来的肯定是出现过一次元素的异或和
  2. 接着，因为这两个元素不同，所以，这两个数字的异或和肯定有一位为1，假设第k位为1
  3. 那么将第k位为1的分为一堆，其余的分为另一堆
  4. 接下来的问题就是 列表中只有一个出现一次的数字，其余的出现两次这个问题了

    【释】：这两堆肯定是第k位为1的为一堆，该堆中只有一个出现过一次，其余的数出现两次，最后，对这两堆分别求异或和就可以求出来了

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> singleNumber(vector<int>& nums) {
    int s = 0;
    for(auto x : nums)
        s ^= x;
    int k = 0;
    while( !(s >> k & 1) )
        k++;
    int s1 = 0, s2 = 0;
    for(auto x : nums)
        if(x >> k & 1)
            s1 ^= x;
        else
            s2 ^= x;
    return vector<int>({s1, s2});
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> singleNumber(vector<int>& nums) {
    int s = 0;
    for(auto x : nums)
        s ^= x;
    int k = 0;
    while( !(s >> k & 1) )
        k++;
    int s1 = 0;
    for(auto x : nums)
        if(x >> k & 1)
            s1 ^= x;
    return vector<int>({s1, s ^ s2});
}

【释】：因为 $s_1$ ^ $s_2$ = s，那么 s ^ $s_1$ = $s_2$，具体性质详见 位运算的知识点以及常用技巧