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
     
       counts = new HashMap
      
       ();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
       
        
         > iterator = counts.entrySet().iterator();19         while(iterator.hasNext()){20             Map.Entry
         
           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: