首页 > 代码库 > Single Number leetcode java
Single Number leetcode java
题目：
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?
题解：
这道题运用位运算的异或。异或是相同为0，不同为1。所以对所有数进行异或，得出的那个数就是single number。初始时先让一个数与0异或，然后再对剩下读数挨个进行异或。
这里运用到异或的性质：对于任何数x，都有x^x=0，x^0=x
代码如下：
1 public int singleNumber(int[] A) {
2 int result = 0;
3 for(int i = 0; i<A.length;i++){
4 result = result^A[i];
5 }
6 return result;
7 }
2 int result = 0;
3 for(int i = 0; i<A.length;i++){
4 result = result^A[i];
5 }
6 return result;
7 }
同时异或还有性质：
交换律 A XOR B = B XOR A
结合律 A XOR B XOR C = A XOR (B XOR C) = (A XOR B) XOR C
自反性 A XOR B XOR B = A XOR 0 = A
所以对于这个数组来说，因为只有一个数字是single的，所以数组可以表示为 a a b b c c d d e。 那么利用上述规律可以异或结果为 0 0 0 0 e。这样写的代码为：
1 public static int singleNumber(int[] A) {
2 for (int i = 1; i < A.length; i++) {
3 A[i] ^= A[i-1];
4 }
5 return A[A.length-1];
6 }
2 for (int i = 1; i < A.length; i++) {
3 A[i] ^= A[i-1];
4 }
5 return A[A.length-1];
6 }
Reference：
http://www.cnblogs.com/hiddenfox/p/3397313.html
http://wezly.iteye.com/blog/1120823
Single Number leetcode java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。