【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：

解法不少，贴一种：

1 class Solution:
2     # @param {integer[]} nums
3     # @return {integer}
4     def singleNumber(self, nums):
5         ans = nums[0];
6         for i in range(1, len(nums)):
7             ans ^= nums[i]
8         return ans

其依据在于：

1、异或运算满足交换律；

2、a ^ a = 0;

3、b ^ 0 = b。

这题的关键就在于线性时间内把相同的一对 “消掉”，留下那个 “落单” 的。

异或运算给了这样的快捷的可能。

【LeetCode】Single Number

原文：http://www.cnblogs.com/maples7/p/4483196.html