Boyer-Moore 投票算法(求众数)

今天刷题刷到了一个有意思的算法

题目为求一个数组的众数

大概思路是:先选第一个数是candidate(众数),初始化count=0。从前往后遍历数组遇到与当前

candidate相等就count+1,不相等就count-1。当count == 0时 candidate等于当前数组遍历到的那个数。遍历结束candidate就是这个数组的众数。

emm...可能表述不太清楚,直接看代码吧

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

//作者:LeetCode-Solution
//链接:https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
//来源:力扣(LeetCode)
//著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

没有一个梦想是傻逼的

上一篇:Mybatis-plus自动生成代码(逆向工程????)


下一篇:Spring 实例化--谁是我的候选人