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     }

 同时异或还有性质:

 交换律 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 }

Reference:

http://www.cnblogs.com/hiddenfox/p/3397313.html

http://wezly.iteye.com/blog/1120823

 

Single Number leetcode java

上一篇:Spring源码阅读:IOC容器之BeanFactory


下一篇:Netty章节二十三:Netty自定义实现粘包与粘包