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;
}
};
上一篇: 移动轨迹回放