摩尔投票算法基础理论及最佳实践

会议大厅站满了投票代表,每个都有一个牌子上面写着自己所选的候选人的名字。然后选举意见不合的(所选的候选人不同)两个人,会打一架,并且会同时击倒对方。

这里意见不合的两个人促成了算法的核心思想:对拼消耗

显而易见,如果一个人拥有的选票比其它所有人加起来的选票还要多的话,这个候选人将会赢得这场“战争”,当混乱结束,最后剩下的那个代表(可能会有多个)将会来自多数人所站的阵营。但是如果所有参加候选人的选票都不是大多数(选票都未超过一半),那么最后站在那的代表(一个人)并不能代表所有的选票的大多数。因此,当某人站到最后时,需要统计他所选的候选人的选票是否超过一半(包括倒下的),来判断选票结果是否有效。

    /*
       求多数元素(众数)
       摩尔投票法
    */
    public int majorityElement1(int[] nums) {
        int count = 0;//当前记录出现次数
        int current = -1;//当前记录值
        for (int num : nums) {
            if (num == current) count++;
            if (num != current) {
                if (count == 0) {
                    current = num;
                } else {
                    count--;
                }
            }
        }
        return current;
    }

评论