LeetCode Q136 Single Number(Medium)

Given an array of integers, every element appears twice except for one. Find that single one.

翻译

给定一个整型数组，除了其中一个元素出现一次，其他每个元素都出现两次。找出出现一次的元素。

分析

解法一：

　　第一反应就是排序并遍历所有元素，计算每个元素出现的次数，然后输出只出现一次的元素，这样的时间复杂度为 O(log₂n) ，空间复杂度为 O(N) 。时间复杂度已经十分理想，但是空间复杂度不稳定，如果数据为 100M、1G ，甚至 10G 的，那么空间申请也严重影响了效率，并且内存条岂不是爆炸了！？现在的问题是解决空间复杂度的问题。

解法二：

　　哪么那些数据可以提前删除呢？解法一中，如果一个元素出现两次，那这个元素就不是要找的元素，就可以删除统计它们出现次数元素。根据这一点，可以使用哈希表，遍历元素时，如果这个元素出现两次，就在哈希表中删除这个元素。时间复杂度为 O(n) ，空间复杂度最好为 O(1)，最差为O(n / 2 + 1)。

解法三：

　　异或的使用：

　A ⊕ A = 0 

　交换律：A ⊕ B = B ⊕ A  

　结合律：A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C 

　　可以看出当有两个相同的数异或时，变为 0 。

　　说到这里，大家应该都想到了方法，把所有数都异或一次，除了只出现一次的元素就会留下。

　　算法就很简单，读入加异或，便得出答案。

int n=0;
n = int.Parse(Console.ReadLine());
int ans=0;
for (int i=0;i<n;i++)
    a ^ = int.Parse(Console.ReadLine());
Console.WriteLine(a.ToString());