[Leetcode] Single Number

时间：2014-10-16 05:08:03 阅读：169 评论：0 收藏：0 [点我收藏+]

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

原文：http://www.cnblogs.com/Phoebe815/p/4027899.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)