Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

s思路： 1. 現在每個數都出現三次，而有一個數出現一次！出現兩次用xor可以消掉，那么出現三次時，如何把淹沒在三個數中的一個數找出來呢？ 2. 肯定又是一個數學問題。百思不得解。剛開始想到先所有求和，然后對3取余數。單這樣仍然不能顯露這個單數的真面目，只能得到這個數對三的余數。 3. 參考了答案。取所有數的每一位相加，對3取余數，即可得到這個單數這一位是1還是0，依此思路，求出所有32位的bit值然后組裝后就是這個單數。復雜度是32n,仍然是o(n)。這道題和之前的Leetcode 127. Word Ladder類似，都是枚舉所有可能情況，在word ladder中，一個數的所有neighbor是26m個，而這里一個數的bit數32個，也就是說找出一個數的最大工作量是32n。 4. 這里想強調：從一堆數里面找一個數，如果不能一下把這個數“暴露”出來，說明這個數隱藏得很深。無計可施的時候，通常就是思維的層次和問題本身的層次不match，簡單說，思維的層次和問題不在一個世界，那么思維就見不到問題，當然也就見不到問題的答案。記得昨天寫過，看到一個問題，要能在思維里準確的限定這個問題，這個問題有多大、邊界在那里，最差的情況在哪兒，越清楚這些離解決的方法越接近。剛才說，思維和問題不再一個世界，但這兩個世界一定是聯通的。對這個問題來說，自己的思維還停留在整個int上，而這個層次確實沒有方法可以把這個數顯露出來，說明他藏得很深，因此不妨思維也深入一下：不把這個數當成一個整體，而是當成32個bit，也就是重心從一蹴而就的找整個數轉變成一個bit一個bit的解開這個未知數的面紗。如下圖，這種需要一步一步的解開答案的過程，讓我聯想到左邊的解開紅綢布看到神秘的禮物的過程，為了handle這條紅綢，就得細心的牽著一角拉看，然后看到一點禮物的樣子，然后是一半，等這個紅綢cover全部褪去，才可以一窺全貌。這和這道題的思路給人的感覺就幾乎一樣。首先，我們知道這個數有多長，32bit，然后被其他數覆蓋，我們把所有數的每個bit都相加的模3的過程就是牽著紅綢往外拉，一共拉32次，就可以看到這個數的全貌。 5. 這和single number I不同，在那里這個數是被兩個相同的數覆蓋。解決的思路，就是把所有數全部xor即可expose這個未知數。這個過程就和上圖右一樣，直接打開鍋蓋，就可以一下看到這個數。不用一點一點的去=揭開。所以，同樣是找數，用什么方法，就看這個數是藏在什么cover下面。如果是鍋蓋型的，就容易好辦，不需要這么細致就能找到；如果是軟布型的，也好辦了，牽著一個角，一步一步來unveil。 6. 把自己能想所想都全部不加選擇的擺在紙面上，我突然能看到自己思維的形狀了，這算是一個很大的進步！發現自己的思維很喜歡形象，即使沒有形象的抽象的，也希望和有形象的connect在一起，而且經常也能找到具象的食物和抽象的食物對應。還可以繼續這么嘗試，有趣！