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