回顾

在前面两篇文章已经实现了,以及

分析

借助上面水王id出现次数刚好出现一半的分析，其实这里就是找出数组中出现次数前三的元素,具体的分析，见前面两篇文章，其实问题的实质以及分析的基本方向都是相似的。

实现

/**     * @Author fanjiajia     * @Date 下午8:50 2018/12/20     * @Description 长度为N的数组中有3个元素，出现次数都超过N/4,找出这3个元素     **/    public 
    
      T[] func4(T[] arr) {        T[] candidates = (T[]) new Object[3];        int[] nTimes = {0,0,0};        for (int i = 0; i< arr.length; i++) {            if (nTimes[0] == 0) {                candidates[0] = arr[i];                nTimes[0] = 1;            }else if (nTimes[1] == 0) {                candidates[1] = arr[i];                nTimes[1] = 1;            }else if (nTimes[2] == 0) {                candidates[2] = arr[i];                nTimes[2] = 1;            }else if (candidates[0] == arr[i]) {                nTimes[0]++;            }else if (candidates[1] == arr[i]) {                nTimes[1] ++;            }else if (candidates[2] == arr[i]) {                nTimes[2] ++;            }else {                nTimes[0] --;                nTimes[1] --;                nTimes[2] --;            }        }        return candidates;    }
    

最后

生命不息，使劲造