leetcode -- Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

[解题思路]

人生最悲催的事是刚面完试，leetcode就把我面试的题目给刷出来了。。。。

1.O(n) time complexity O(n) space complexity count the ocurrence of every number

 1 public class Solution {
 2     public int singleNumber(int[] A) {
 3         // Note: The Solution object is instantiated only once and is reused by each test case.
 4         int N = A.length;
 5         if(N == 0){
 6             return N;
 7         }
 8         
 9         Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
10         for(int i = 0; i < N; i++){
11             if(counts.containsKey(A[i])){
12                 counts.put(A[i], counts.get(A[i]) + 1);
13             } else {
14                 counts.put(A[i], 1);
15             }
16         }
17         
18         Iterator<Map.Entry<Integer, Integer>> iterator = counts.entrySet().iterator();
19         while(iterator.hasNext()){
20             Map.Entry<Integer, Integer> entry = iterator.next();
21             if(entry.getValue() != 3){
22                 return entry.getKey();
23             }
24         }
25         return 0;
26     }
27 }

2.使用O(1)的空间来解决

 1 public int singleNumber(int[] A) {
 2         // Note: The Solution object is instantiated only once and is reused by each test case.
 3         int N = A.length;
 4         if(N == 0){
 5             return N;
 6         }
 7         
 8         int[] counts = new int[32];
 9         int result = 0;
10         for(int i = 0; i < 32; i++){
11             for(int j = 0; j < N; j++){
12                 if(((A[j] >> i) & 1) == 1){
13                     counts[i] = (counts[i] + 1) % 3;
14                 }
15             }
16             result |= (counts[i] << i);
17         }
18         
19         return result;
20     }

ref:http://www.mitbbs.com/article_t/JobHunting/32547143.html