首页 > 代码库 > Single Number

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?

 1 import java.util.Hashtable; 2 public class Solution { 3     public int singleNumber(int[] A) { 4         Hashtable<Integer, Integer> hashtable = new Hashtable<Integer,Integer>(); 5         int result = 0; 6          7         for(int i = 0; i < A.length;i++){ 8             Integer element = hashtable.get(A[i]); 9             if(null == element){10                 hashtable.put(A[i], 1);//第一次放111             }12             else if(1 == element){13                 hashtable.put(A[i], 2);//第二次放214             }15         }//for16         for(int i = 0; i < A.length; i++){17             if(1 == hashtable.get(A[i])){18                 result = A[i];19                 break;20             }21         }//for22         return result;23     }24 }

 ps

因为题目有要求,用O(1)空间,O(n)时间复杂度,用了hash表后,空间复杂度变为了O(n)

这里可以用异或来处理

异或具有交换性,a ^ b = b ^ a

0 ^ a = a

将所有的A[i]异或起来,A[0] ^ A[1]....这样根据交换性,最后只剩下单个的个数

只扫描了一遍,时间复杂度为O(N),只用了一个存储单元空间复杂度为O(1)

参考:http://www.cnblogs.com/changchengxiao/p/3413294.html

 1 public class Solution { 2     public int singleNumber(int[] A) { 3         int result = 0; 4         for(int i = 0; i < A.length; i++){ 5             result ^= A[i]; 6         } 7          8         return result; 9     }10 }

 

Single Number