题目
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4
一次遍历，常数级的额外空间复杂度
解题
可以利用HashMap直接解决，时间复杂度和空间复杂度都是O(N)
1.map中存在该元素则：map.put(num,map.get(num) + 1)
2.map中不存在该元素则：map.put(num , 1)
3.map中这个元素出现次数等于三次，则删除该元素
空间复杂度最坏的情况是O(N*2/3)
public class Solution { /** * @param A : An integer array * @return : An integer */ public int singleNumberII(int[] A) { // write your code here HashMap<Integer,Integer> map = new HashMap<Integer,Integer>(); int single = 0 ; for(int i=0;i<A.length;i++){ if(map.containsKey(A[i])){ map.put(A[i],map.get(A[i]) + 1); }else{ map.put(A[i],1); } if(map.get(A[i]) == 3){ map.remove(A[i]); } } Set<Integer> keySet = map.keySet(); for( Integer num:keySet){ single = num; } return single; } }
总耗时: 2647 ms
这个方法不是很好，空间复杂度不是O(1)
当a出现一次的时候，ones能保存a。当a出现两次的时候，twos能保存a。
当a出现三次的时候，ones和twos都清零。
所以，如果一个数值中所有的数都通过这个循环的话，出现三次的数都清零了，
有一个数如果出现一次，它保存在ones中；如果出现两次的话保存在twos中。
public class Solution { /** * @param A : An integer array * @return : An integer */ public int singleNumberII(int[] A) { // write your code here int ones = 0; int twos = 0; for(int i=0;i< A.length ;i++){ ones = (ones^A[i]) & (~ twos); twos = (twos^A[i]) & (~ ones); } return ones; } }
总耗时: 246 ms
class Solution: """ @param A : An integer array @return : An integer """ def singleNumberII(self, A): # write your code here ones = 0 twos = 0 for num in A: ones = (ones ^ num) & (~twos) twos = (twos ^ num) & (~ones) return ones
总耗时: 258 ms
表示不理解。。。
lintcode 中等题：Singleton number II 落单的数 II
原文：http://www.cnblogs.com/theskulls/p/4915425.html
