首页 > 代码库 > 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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。