欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LintCode 84: Single Number III (经典位运算题)

程序员文章站 2022-07-05 12:59:10
...

原题如下:
Given 2*n + 2 numbers, every numbers occurs twice except two, find them.

Have you met this question in a real interview?
Example
Given [1,2,2,3,4,4,5,3] return 1 and 5

Challenge
O(n) time, O(1) extra space.

先将所有数统统异或,最后剩下的就是a和b的异或。该异或结果必然不为0,否则a==b。取该异或结果的任意一个非1位便可将所有数分为2类:该位为1的和该位不为1的。
最简便的方法是用x & (-x)返回最右边1的对应值(即Binary Index Tree里面的LowBit(x))方法。

class Solution {
public:
    /**
     * @param A: An integer array
     * @return: An integer array
     */
    vector<int> singleNumberIII(vector<int> &A) {
        int xor_v = 0;

        for (auto i : A) {
            xor_v ^= i;
        }
        
        int lastOne = xor_v & (-xor_v);
        
        vector<int> result = {0, 0}; //result[0] and result[1] are two categories
        
        for (auto i : A) {
            if (i & lastOne)
                result[0] ^= i;
            else
                result[1] ^= i;
        }
        
        return result;
    }
};
相关标签: LintCode