面试题：如何找出数组里出现次数超过总数1/3的数

　　给你一个数组nums，如何找nums中出现次数超过总数的1/3的数，要求时间复杂度O(N)和空间复杂度O(1)。我觉得这不算是一道算法题，更像是一道智力题。接下来我先说下这道题怎么做，再谈谈我对此类题的看法。

　　首先，看下题目要求，时间复杂度O(1)，于是就可以排除一些常规的简单做法了，比如暴力（O(n^2)），排序（时间复杂度O(Nlogn)），计数（空间复杂度O(n)）……脑子里回顾一遍所有的算法，似乎没啥算法能用的上（常见算法要么时间换空间，要么空间换时间），这个时候我们就要另辟蹊径了。。
　　如果你每次从nums中拿出3个不一样的数作为一组，肯定会出现两种情况。一，nums被取空了，那么nums中每个数出现次数最多占总次数的1/3，写代码很好处理吧！！ 二，还有剩余，这个情况就复杂了，有可能剩余多个，但是……但是，最多只可能剩余两种数。 为什么？ 3个不同的数凑一组才能删掉，所以不可能删掉超过1/3的数。所以超过1/3的数肯定被剩下来，但是，剩下来的俩数并不一定都是超过1/3的，这点额外注意。 很容易举个例子， 比如

 1 1 1 1 1 2 2 3 3 4 4 5

　　像上面这种情况，有可能剩下１ ４，但4并没有超过1/3，所以还需要对剩下的俩数重新计数才能确认。
　　看起来我们把原问题转换为如何快速高效的从数组中每次去掉3个不同的数，似乎又是一个难题。不就是俩数吗，我就把这俩数保存起来，再加俩计数器来计数他们俩最终还剩下多少个。这里也许很难理解，这么说吧，我先遍历nums，在遍历过程中如果凑够3个不一样的就丢掉这3个数。看下代码就很容易理解了。

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public List<Integer> findNums(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<Integer>();
        if (nums.length == 0)
            return ans;
        int a, cnta = 0;  //我用a b分别表示两个不一样的数
        int b, cntb = 0;
        for (int i = 0; i < nums.length; i++) {
            if (cnta > 0 && cntb > 0) {
                //如果a b不空，切当前遍历的到的数和a b都不一样，表示可以凑一组删掉了。 
                if (nums[i] != a && nums[i] != b) {
                    cnta--;
                    cntb--;
                }
                // 如果等于其中某个数，该计数器加1
                else if (a == nums[i]) {
                    cnta++;
                }
                else {
                    cntb++;
                }
            }
            //接下来两种情况是如果a和b其中之一为空。
            else if (cnta > 0 && 0 == cntb){
                if (nums[i] == a) {
                    cnta++;
                }
                else {
                    b = nums[i];
                    cntb++;
                }
            }
            else if (0 == cnta && cntb > 0) {
                if (nums[i] == b) {
                    cntb++;
                }
                else {
                    a = nums[i];
                    cnta++;
                }
            }
            //a b都为空，就把当前数放到a里。
            else {
                a = nums[i];
                cnta++;
            }
        }
        if (cnta > 0) {
            cnta = 0;
            for (int i = 0; i < nums.length; i++) {
                if (a == nums[i])
                    cnta++;
            }
            if (cnta >= nums.length/3)
                ans.add(a);
        }
        if (cntb > 0) {
            cntb = 0;
            for (int i = 0; i< nums.length; i++) {
                if (b == nums[i])
                    cntb++;
            }
            if (cntb >= nums.length/3)
                ans.add(b);
        }
        if (cnta == 0 && cntb == 0 && nums.length != 0) {
            //if there are three unique number, return them. else return null.
        }
        return ans;
    }
}

　　代码写的比较长，可能不是很好读，但思路是对的，最后那个if里我省略掉了一些代码，其实就是上文中说的情况一。
　　其实这种题目还是比较考验应聘者的，首先要能想到要摒弃所学算法，可以证明应聘者对算法还是有一定理解的。如果应聘者真能想到上面的解法，说明思维还是比较灵活的。但是思维灵活和聪明还是有区别的，每个人处理问题的方式和其阅历有想当大的关系，我能想到这个解法，其实是因为我好像见过超过1/2的，当然你看过这个之后，你就能解决1/2,，1/4，1/5……的题了。。

~谢谢打赏~

赏