Leetcode 137. Single Number II

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在一起，而且经常也能找到具象的食物和抽象的食物对应。还可以继续这么尝试，有趣！