Home LeetCode-260 Single Number III
Post
Cancel

LeetCode-260 Single Number III

Description

给定一个数组\(nums[]\),里面有2个数只出现一次,其它数只出现两次,找出前者

Constraints

要求\(O(n)\)时间复杂度,\(O(1)\)空间复杂度

Solution

二进制分组。设\(sum\)为xor之和,\(a, b\)为答案,由性质可知\(sum = a \oplus b\)

但是这个时候仍不足以区分答案。进一步发现\(sum\)里面必然有一个位设为1,以此作为二进制分组

划分为2组后就是低配版Single Number问题

Code

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int sum = 0;
        for(auto v : nums) sum ^= v;
        int pos;
        for(int i = 0; i < 32; ++i) {
            if(sum >> i & 1) {
                pos = i;
                break;
            }
        }
        int g[2] {};
        for(auto v : nums) {
            g[v >> pos & 1] ^= v;
        }
        return {g[0], g[1]};
    }
};

LeetCode-260 Single Number III

This post is licensed under CC BY 4.0 by the author.
Contents