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(n)，则称这个算法具有线性时间，或O(n)**时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如，一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。这个描述是稍微不准确的，因为运行时间可能显著偏离一个精确的比例，尤其是对于较小的n。
PS：note中的内容是可选的，而不是必须的。毕竟O(n)的算法不是随随便便就能想到的。
错误的思路：先排序，然后使用两个数相同的话，相加必定是偶数即％2＝0，可是却忽略了那个落单的数也有可能是偶数。。阿西吧。
正确的思路：先排序，然后用这个数必定和另外的数没有相等的数，一次性比较两个数。观察多组这样的数可知，落单的数字必定是在偶数的位置上（虽然好像没什么用。）
那么算法就出来了（js）：
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
if(nums.length==1)
return nums[0];
nums.sort(function(a,b){return a-b;});
for(var i=0;i<=nums.length;){
if(nums[i]==nums[i+1])
i+=2;
else
return nums[i];
}
};
接下来说说O(n)的解法吧：
你可以直接戳https://oj.leetcode.com/discuss/6170/my-o-n-solution-using-xor
也可以听我的简单讲解。
使用的是XOR（异或）即两者不同时为真，相同时为假。下图为js语法：
我具体解释一下异或。
example:
console.log(4^5) //1
reason:
十进制的4的二进制为0000 0100，十进制的5的二进制为0000 0101。每一位和每一位相对应：
那么如果两个一样的数字异或的话会怎样？可以知道的是直接变成0，如果0和其他的数字异或会怎样？可以知道的是不会改变。不信的话可以自己将其变成二进制，然后按位异或试试。
那么这个O(n)的算法使用了这个特性。并且，多个数异或的话，程序会自动变换位置将相同的放在一起异或（这简直是bug）像这样：
(2^1^4^5^2^4^1) => ((2^2)^(1^1)^(4^4)^(5)) => (0^0^0^5) => 5
那么O(n)的算法代码如下(C)：
int singleNumber(int A[], int n) {
int result = 0;
for (int i = 0; i<n; i++) {
result ^=A[i];
}
return result;
}
会用xor的真厉害呢(:з」∠)
