求n个数中出现个数超过n/3的元素

要求空间复杂度O(1)。

思路：方便起见，先假设答案是a。首先我定义3个组，然后取3个数，按照它们3个两两是否相同划分到1~3个组里。接下来我们重复这样的过程：踢一轮、取1个、踢一轮、取1个……
踢是这么操作的：如果这3个组每个组都不空，那么我每个组都踢掉一个，直到出现至少1个空组。这样做是因为如果某一轮我踢掉了一个答案a，那么我一定同时踢掉了2个非a，如果某一轮没有踢a，那我一定踢掉了3个非a。
然后再取1个x：踢完一轮后至少有1个空组，如果x属于某个非空组，就把它放进去，否则就利用那个空组，把空组设为x的组。
这样先踢再取再踢，直到把所有数取完。这时剩下至多2个非空组，所有被踢掉的数中a不超过1/3，所以剩下的数中a不少于1/3，所以如果三组全空，则不存在这样的a，如果只剩下1组，这组所代表的数值就是答案a，如果剩下2组，答案无从确定，再对原数据扫一边从而判断即可。