编程练习：寻找发帖"水王"扩展问题一

回顾

寻找发帖水王的问题总结起来就是在一个数组中某一个元素出现次数超过了数组长度的一半，那么可以很顺利的找到这个元素，实现见"编程练习:寻找发帖水王"

扩展

上面的问题中，强调了某一个元素出现次数超过了数组长度的一半，那么试想一下，如果这个元素刚好只有一半, 比如{1,2,3,1,2,1};那么按照上面的思路和实验结果，其结果是2，显然出现和预期不符合的答案。

分析

其实可以发现这个元素刚好只出现了一半，那么我们可以在遍历时同时预备两个元素，该思想要达到的效果就是能够找出数组中出现次数第一和第二多的两个变量，那么问题就迎刃而解。

实现

直接上代码, 相应的分析，上面的文章已经很透彻

/**

     * @Author fanjiajia

     * @Date 下午8:11 2018/12/20

     * @Description 数组中某个元素出现次数刚好只有数组长度的一半，找出它

     **/

    public <T> T func3(T[] arr) {

        T[] candidates = (T[]) new Object[2];   // 泛型类数组的创建

        int[] nTimes={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 (candidates[0] == arr[i])

                nTimes[0] ++;

            else if (candidates[1] == arr[i])

                nTimes[1] ++;

            else {

                nTimes[0]--;

                nTimes[1]--;

            }

        }

       return nTimes[0] > nTimes[1]? candidates[0]:candidates[1];

    }

最后

生命不息，使劲造

巴特西

编程练习：寻找发帖"水王"扩展问题一

回顾

扩展

分析

实现

最后

最新文章

热门文章