摩尔投票法

一般用法

概念

解决的问题：在任意多的候选人中选出票数超过一半的那个人。和哈希法相比，只有常量级的空间复杂度，哈希表需要开辟额外的空间，需要线性空间复杂度

前提：票数要超过一半，这样就可以得到一个结论就是票数超过一半的人至多只有一个

大致过程：

• 投票阶段：从前往后统计候选人的票数，如果票相同，那么票数+1；如果票不同，那么票数-1，当票数为0时需要更换候选人
• 计数阶段：在抵消阶段最后得到的抵消计数只要不为 0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定

详细过程： 假设投票情况是这样的：[A, B, A, B, C, A, A] ，其中 A B C 代表不同的候选人，然后从前往后遍历

• 当前一张选票和后一张选票是相同的时候，那么这个候选人的票数 +1

• 当前一张选票和后一张选票不是相同的时候，那么这个候选人的票数 -1；而且当这个候选人的票数减到为 0 时，就要把候选人更换为当前票代表的候选人，并把票数重置为1

• 再次遍历确定候选人票数是否超过一半

使用一个表格来表示这个投票的过程，投票情况：[A, B, A, B, C, A, A]

	候选人	票数	备注
初始化	A	0	初始化时把候选人初始化为第一个元素
i = 0	A	1	匹配，票数+1
i = 1	A	0	不匹配，票数-1
i = 2	A	1	匹配，票数+1
i = 3	A	0	不匹配，票数-1
i = 4	C	1	当票数=0，更换候选人，重置票数为1
i = 5	C	0	不匹配，票数-1
i = 6	A	1	当票数=0，更换候选人，重置票数为1

最后遍历数组时发现 A 出现的次数为 4，$4>(7/2=3)$ 所以结论：A 是那个出现次数最多的元素

如果仅凭投票阶段是没有办法验证的，例如把最后一张票改成 C，投票情况最终变成这样：[A, B, A, B, C, A, C] ，投票阶段得出的结果是 C ，但是 C 却不满足出现次数超过一半的条件

代码实现

public int majorityElement3(int[] nums) {
    int candidate = nums[0], count = 0;
    // 投票阶段
    for (int num : nums) {
        // 如果和候选人匹配上,那么候选人的票数+1
        if (candidate == num) {
            count++;
            continue;
        }
        // 如果和候选人不匹配,且候选人的票数扣光了
        // 那么更换候选人为当前元素,且把票数重置为1
        if (count == 0) {
            candidate = num;
            count = 1;
            continue;
        }
        // 如果和候选人没有匹配上,且还有票数,那么票数-1
        count--;
    }
    // 计数阶段
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }
    // 检查是否超过一半
    if (count > nums.length / 2) {
        return candidate;
    }
    return -1;
}

推广用法

概念

摩尔投票法不仅仅能用于统计票数超过一半的人，还可以推广成统计出现次数超出「n/k」的数，k为大于等于2的自然数，n为数组长度

并且可以得出以下结论：出现次数超出「n/k」的数最多只有 k-1 个

同样的过程也是分为投票阶段和计数阶段

• 投票阶段，因为能确定候选人最多只有 k-1 个，所以初始化时初始 k-1 个候选人，后续与一般用法类似

• 计数阶段几乎和一般用法一样，就是统计候选人的票数是否大于 n/k

详细过程使用 k=3 的情况来阐述：

投票情况是 [A, B, C, A, A, B, C] ，其中 A B C 代表不同的候选人，然后从前往后遍历

• 如果和候选人1匹配上了，那么候选人1的票数+1
• 如果和候选人2匹配上了，那么候选人2的票数+1
• 如果和候选人1、2都没有匹配上，且候选人1的票数扣光了，那么候选人1更换为当前元素，且票数重置为1
• 如果和候选人1、2都没有匹配上，且候选人2的票数扣光了，那么候选人2更换为当前元素，且票数重置为1
• 如果和候选人1、2都没有匹配上，且两个候选人的票数都还有，那么候选人1、2的票都要抵扣

用表格来表示投票的过程

	候选人1	票数1	候选人2	票数2	备注
初始化	A	0	A	0	初始化时把候选人都初始化为第一个元素
i = 0	A	1	A	0	候选人1匹配，票数+1
i = 1	A	1	B	1	候选人2票数=0，更换候选人，重置票数为1
i = 2	A	0	B	0	票和两个候选人都不匹配，两个候选人的票数都-1
i = 3	A	1	B	0	候选人1匹配，票数+1
i = 4	A	2	B	0	候选人1匹配，票数+1
i = 5	A	2	B	1	候选人2匹配，票数+1
i = 6	A	1	B	0	票和两个候选人都不匹配，两个候选人的票数都-1

最后遍历数组时发现 A 出现的次数为 3，$3>(7/3=2)$；B 出现的次数为 2，$2=(7/3=2)$，所以最终的候选人是 A。所以看到单靠投票阶段是无法最终确定候选人的，这里经过投票阶段后 A 和 B 的票数都有可能超过 7/3，但是需要最终的计数阶段。

代码实现

public List<Integer> majorityElement2(int[] nums) {
    // 出现超过 n/3 次的元素一定小于等于 3-1=2 个
    List<Integer> result = new ArrayList<>(2);
    // 投票阶段
    int candidate1 = nums[0], candidate2 = nums[0];
    int count1 = 0, count2 = 0;
    for (int num : nums) {
        // 如果和候选人1匹配上了,那么候选人1的票数+1
        if (candidate1 == num) {
            count1++;
            continue;
        }
        // 如果和候选人2匹配上了,那么候选人2的票数+1
        if (candidate2 == num) {
            count2++;
            continue;
        }
        // 如果和候选人1、2都没有匹配上，且候选人1的票数扣光了
        // 那么候选人1更换为当前元素，且票数重置为1
        if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
            continue;
        }
        // 如果和候选人1、2都没有匹配上，且候选人2的票数扣光了
        // 那么候选人2更换为当前元素，且票数重置为1
        if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
            continue;
        }
        // 如果和候选人1、2都没有匹配上，而且候选人1、2的票数都扣光了
        // 那么同时抵扣两个候选人的票数
        count1--;
        count2--;
    }
    // 计数阶段
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        }
    }
    // 出现次数超过 n/3 的元素可以放入到最后的结果中
    if (count1 > nums.length / 3) {
        result.add(candidate1);
    }
    if (count2 > nums.length / 3) {
        result.add(candidate2);
    }

    return result;
}

leetcode169.多数元素

题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

例子：

输入：[2, 2, 1, 1, 1, 2, 2]，输出：2

这道题目满足摩尔投票法的前提，使用摩尔投票法可以轻松解决

public static int majorityElement(int[] nums) {
    int candidate = nums[0], count = 0;
    // 投票阶段
    for (int num : nums) {
        // 如果和候选人匹配上,那么候选人的票数+1
        if (candidate == num) {
            count++;
            continue;
        }
        // 如果和候选人匹配上,且票数扣光了
        // 那么更换候选人为当前元素,且把票数重置为1
        if (count == 0) {
            candidate = num;
            count = 1;
            continue;
        }
        // 如果和候选人没有匹配上,且还有票数,那么票数-1
        count--;
    }
    // 计数阶段
    count = 0;
    for (int num : nums) {
        if (num == candidate) {
            count++;
        }
    }
    // 检查是否超过一半
    if (count > nums.length / 2) {
        return candidate;
    }
    return -1;
}

leetcode229.多数元素Ⅱ

题目：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

例子1： 输入：nums = [3,2,3]，输出：[3]

例子2： 输入：nums = [1,2]，输出：[1,2]

这道题可以使用摩尔投票法的推广用法，k=3，所以满足条件最多只有2个

public static List<Integer> majorityElement(int[] nums) {
    // 出现超过 n/3 次的元素一定小于等于 3-1=2 个
    List<Integer> result = new ArrayList<>(2);
    // 投票阶段
    int candidate1 = nums[0], candidate2 = nums[0];
    int count1 = 0, count2 = 0;
    for (int num : nums) {
        // 如果和候选人1匹配上了,那么候选人1的票数+1
        if (candidate1 == num) {
            count1++;
            continue;
        }
        // 如果和候选人2匹配上了,那么候选人2的票数+1
        if (candidate2 == num) {
            count2++;
            continue;
        }
        // 如果和候选人1、2都没有匹配上，且候选人1的票数扣光了
        // 那么候选人1更换为当前元素，且票数重置为1
        if (count1 == 0) {
            candidate1 = num;
            count1 = 1;
            continue;
        }
        // 如果和候选人1、2都没有匹配上，且候选人2的票数扣光了
        // 那么候选人2更换为当前元素，且票数重置为1
        if (count2 == 0) {
            candidate2 = num;
            count2 = 1;
            continue;
        }
        // 如果和候选人1、2都没有匹配上，而且候选人1、2的票数都扣光了
        // 那么同时抵扣两个候选人的票数
        count1--;
        count2--;
    }
    // 计数阶段
    count1 = 0;
    count2 = 0;
    for (int num : nums) {
        if (num == candidate1) {
            count1++;
        } else if (num == candidate2) {
            count2++;
        }
    }
    // 出现次数超过 n/3 的元素可以放入到最后的结果中
    if (count1 > nums.length / 3) {
        result.add(candidate1);
    }
    if (count2 > nums.length / 3) {
        result.add(candidate2);
    }

    return result;
}

总结

摩尔投票法的适用场景：在任意多的候选元素中选出出现次数超过 k 次的 k-1 个元素

摩尔投票法的两个阶段

• 投票阶段：从前往后统计候选元素的票数，如果票相同，那么票数+1；如果票不同，那么票数-1，当票数为0时需要更换候选人

• 计数阶段：在抵消阶段最后得到的抵消计数只要不为 0，那这个候选人是有可能超过一半的票数的，为了验证，则需要遍历一次，统计票数，才可确定