[LintCode/LeetCode] Single Number III
文章目录
Problem
Given 2*n + 2 numbers, every numbers occurs twice except two, find them.
Example
Given [1,2,2,3,4,4,5,3] return 1 and 5
Challenge
O(n) time, O(1) extra space.
Note
n & (n-1): 去掉最后一个1;
n & (-n): 保留最后一个1;
n & (~(n-1)): 保留最后一个1;
Integer.highestOneBit(n): 保留第一个1;
这道题在LC论坛里参考了huangjingshu和zhiqing_xiao两位仁兄的解法。思想是:
将A中所有的数进行异或运算。不同的两个数异或的结果diff,一定至少有一位为1。我们只保留diff中的一个1,可以是第一个1,也可以是最后一个1,假设这个1在第i位好了!
然后再次将A中所有的数num和diff相与:
若num & diff的结果为diff,说明这些num的第i位是1:将num与res0异或后存入res0,这样最后异或出来的结果就是两个single number中第i位是1的那个;
同理,若num & diff的结果为0,说明这些num的第i位是0:将num与res1异或后存入res1,这样最后异或出来的结果就是两个single number中第i位是1的那个。
最后,将res1和res0存入res数组,返回。
Solution
public class Solution {
public List<Integer> singleNumberIII(int[] A) {
int diff = 0;
for (int num: A) {
diff ^= num;
}
//diff &= -diff;
diff &= ~(diff-1);
int res0 = 0, res1 = 0;
for (int num: A) {
if ((diff & num) == diff) res0 ^= num;
else res1 ^= num;
}
List<Integer> res = new ArrayList();
res.add(res0);
res.add(res1);
return res;
}
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论