A Za, A Za, Fighting...

題目：

1. 給你n個數(shù)，其中有且僅有一個數(shù)出現(xiàn)了奇數(shù)次，其余的數(shù)都出現(xiàn)了偶數(shù)次。用線性時間常數(shù)空間找出出現(xiàn)了奇數(shù)次的那一個數(shù)。
2. 給你n個數(shù)，其中有且僅有兩個數(shù)出現(xiàn)了奇數(shù)次，其余的數(shù)都出現(xiàn)了偶數(shù)次。用線性時間常數(shù)空間找出出現(xiàn)了奇數(shù)次的那兩個數(shù)。

答案：

1. 從頭到尾異或一遍，最后得到的那個數(shù)就是出現(xiàn)了奇數(shù)次的數(shù)。這是因為異或有一個神奇的性質(zhì)：兩次異或同一個數(shù)，結果不變。再考慮到異或運算滿足交換律，先異或和后異或都是一樣的，因此這個算法顯然正確。

2. 從頭到尾異或一遍，你就得到了需要求的兩個數(shù)異或后的值。這兩個數(shù)顯然不相等，異或出來的結果不為0。我們可以據(jù)此找出兩個數(shù)的二進制表達中不同的一位，然后把所有這n個數(shù)分成兩類，在那一位上是0的分成一類，在那一位上是1的分到另一類。對每一類分別使用前一個問題的算法。