A Za, A Za, Fighting...

題目：

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

答案：

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

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