隨筆檔案

一個字符串由 a - z 26 個字符組成，其中只有一個字符出現的次數為奇數次，其他 25 個字符出現次數都是偶數次。

找出這個出現奇數次的字符。

這個問題，最直觀的解法就是遍歷一下，記錄每個字符的出現次數 int x[26] = {0};

然后掃描 x 檢測即可。

但是回過頭來想一下這樣做有必要嗎，看看我們這樣做的后果是什么，我們得到了所有字符出現的次數，然后檢測以得到出現次數為奇數的字符，這種方法是可以的，但是沒有必要得到每個字符的出現次數，也就是說我們得到了大量的冗余信息，這種冗余信息是需要代價的。這也就導致了我們的這種方法效率不高。

把問題認識清楚很重要，最重要。我們只需要找到出現次數為奇數的字符，不需要得到每個字符的具體出現次數。我們可以利用位運算中的異或。

異或的運算性質是：

a ^ a = 0

a ^ a ^ a = a

偶數個本身異或運算為 0

奇數個本身異或運算為其本身

也就是說，我們可以對字符串中的每個字符，一遍掃描，做異或運算，由于 25 個字符出現偶數次，1 個字符出現奇數次，一遍掃描異或運算得到的結果即是出現次數為奇數的那個字符。

總結：
一個問題的解決，要從認清問題開始。求解問題的好的方法是觀察我們的解決過程，看看是不是中間得到了冗余的信息，如果存在這種冗余信息，說明我們的解法做了不必要的計算，有更大的改進空間。

異或運算很巧妙。關于它的巧妙運用很多地方都有提到。其中《編程之美》中有關于異或運算的運用。