LeetCode 137 - Single Number II

作者 QIFAN 日期 2016-12-21
LeetCode 137 - Single Number II

原题链接:137. Single Number II


题目

给定一列数组,其中每个元素都有三个重复除了一个。找出单个的那个数。

思路

通常第一反应就是排序,然后进行数数。我也是只有这一个想法。
排序花费 $nlogn$ ,遍历花费 $n$,所以时间复杂度还是 $O(n)$

虽然我有一种隐约的想法可以用位运算,因为一个数与自身 “^” 结果为 0 。看了论坛里牛牛,更加云里雾里里。献上代码:

public class Solution {
public int singleNumber(int[] nums) {
//we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
//#curent income ouput
//# ab c/c ab/ab
//# 00 1/0 01/00
//# 01 1/0 10/01
//# 10 1/0 00/10
// a=~abc+a~b~c;
// b=~a~bc+~ab~c;
int a=0;
int b=0;
for(int c:nums){
int ta=(~a&b&c)|(a&~b&~c);
b=(~a&~b&c)|(~a&b&~c);
a=ta;
}
//we need find the number that is 01,10 => 1, 00 => 0.
return a|b;
}
}