Single Number

Single Number

 

Given an array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Naive Way:好有纪念意义的一道题啊，这是我做leetcode的第一道题，对我有启蒙之恩。当时竟不知道Map为何物，更惶论HashTable了。

即使不知道这些也是可以做的，这是我第一次的做法。

 public int singleNumber(int[] A) {  
     int map[] = new int[(A.length+1)/2];  
     int len = map.length;  
     int temp;  
     // 0 case && 1 case  
     int count0 = 0;  
     int count1 = 0;  
     for(int i = 0;i < A.length;i++){  
       if(A[i] == 0){  
         count0++;  
       }  
       if(A[i] == 1){  
         count1++;  
       }  
     }  
     if(count0 == 1){  
       return 0;  
     }  
     if(count1 == 1){  
       return 1;  
     }  
     // general case  
     for(int i = 0;i < A.length;i++){  
       temp = Math.abs(A[i]%len);  
       while(map[temp] != 0 && map[temp] != A[i]){  
         temp++;  
         temp = temp%len;  
       }  
       if(map[temp] == 0){  
         map[temp] = A[i];  
       }else if(map[temp] == A[i]){  
         map[temp] = 1;  
       }  
     }  
     for(int i = 0;i < len;i++){  
       if(map[i] != 0 && map[i] != 1){  
         return map[i];  
       }  
     }  
     return 0;  
   }  

Improved Way: 现在我知道 a^a = 0这回事了。

 

  public class Solution {  
   public int singleNumber(int[] A) {  
     int x = 0;  
     for(int i = 0;i < A.length;i++) x ^= A[i];  
     return x;  
   }  
 }