摩尔投票法

摩尔投票法

力扣剑指Offer39题

• 票数和：由于众数出现的次数超过数组长度的一半；若记众数的票数为 +1 ，非众数的票数为 -1 ， 则一定有所有数字的票数和 > 0
• 票数正负抵消： 设数组 nums 中的众数为 x，数组长度为 n。若nums 的前a个数字的 票数和 = 0，则数组后（n-a）个数字的 票数和一定仍 > 0 （即后（n-a）个数字的 众数仍为x）。

算法原理：

• 为构建正负抵消，假设数组首个元素n₁为众数，遍历统计票数，当发生正负抵消时，剩余数组的众数一定不变

  • 当n₁ = x ：抵消的数字中，有一半是众数x
  • 当n₁ != x ：抵消的所有数字中，少于或等于一半是众数x。

• 利用此特性，每轮假设都可以缩小剩余数组区间。当遍历完成时，最后一轮假设的数字即为众数

public int majorityElement(int[] nums) {
        int x = 0, votes = 0;
        for(int num : nums){
            if(votes == 0) x = num;
            votes += num == x ? 1 : -1;
        }
        return x;
    }