堅信：勤能補拙
題目：
答案：
從頭到尾異或一遍，最后得到的那個數就是出現了奇數次的數。這是因為異或有一個神奇的性質：兩次異或同一個數，結果不變。再考慮到異或運算滿足交換律，先異或和后異或都是一樣的，因此這個算法顯然正確。
從頭到尾異或一遍，你就得到了需要求的兩個數異或后的值。這兩個數顯然不相等，異或出來的結果不為0。我們可以據此找出兩個數的二進制表達中不同的一位，然后把所有這n個數分成兩類，在那一位上是0的分成一類，在那一位上是1的分到另一類。對每一類分別使用前一個問題的算法。
posted on 2011-09-04 15:37 simplyzhao 閱讀(224) 評論(0) 編輯 收藏 引用 所屬分類: R_找工復習2011