感谢：http://www.cnblogs.com/changchengxiao/p/3413294.html

Single Number

Total Accepted: 103007 Total Submissions: 217483 Difficulty: Medium

 

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?

 

琢磨了很久没找到满足题目的两个要求：O(1)和不开空间。实在没办法才上网查找，原来是汇编语言的知识，而且C++中还可以直接用。

 

原文：

o(n)的算法只能是线性扫描一遍，可能的相法是位运算。对于异或来说：1. 异或运算是可交换，即 a ^ b = b ^ a2. 0 ^ a = a那么如果对所有元素做异或运算，其结果为那个出现一次的元素，理解是a1 ^ a2 ^ ....

 

所以说，这是终极解法。

 

1 public class Solution { 2     public int singleNumber(int[] A) { 3         // Note: The Solution object is instantiated only once and is reused by each test case. 4         if(A == null || A.length == 0){ 5             return 0; 6         } 7         int result = A[0]; 8          9         for(int i = 1; i < A.length; i++){10             result ^= A[i];11         }12         return result;13     }14 }

 

LeetCode很有趣，希望明天可以自己想出来！