首页 > 代码库 > [Leetcode] Single Number

[Leetcode] 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?

Solution:

XOR

Information about XOR:

异或运算的几个相关公式:

1. a ^ a = 0
2. a ^ b = b ^ a
3. a ^ b ^ c = a ^ (b ^ c) = (a ^ b) ^ c
4. d = a ^ b ^ c 可以推出 a = d ^ b ^ c
5. a ^ b ^ a = b
 
本题可以抽象成:int数组里有x1, x2 ... xn(每个出现2次),和y(只出现一次),得出y的值。
由公式2可知,数组里面所有数异或的结果等于 x1^x1^x2^x2^...^xn^xn^y
由公式3可知,上式等于(x1^x1)^(x2^x2)^...^(xn^xn)^y
由公式1可知,上式等于(0)^(0)^...(0)^y = y
 
因此只需要将所有数字异或,就可得到结果。
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         return result;8     }9 }

 

[Leetcode] Single Number