力扣（LeetCode） - 229 求众数

本题可以摩尔投票法来解决

一、题目

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

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例1:

输入: [3,2,3]
输出: [3]

示例2:

输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

二、思路

找到出现超过⌊ n/3 ⌋ 次的元素，那么元素个数最多是两个。
摩尔投票法：
如果求出现超过⌊ n/2 ⌋ 次的元素，每次从元素中找到两个不同的元素并删除，最后一定会留下0个或者1个元素。
在程序中可以这样表示：用一个数字 num 表示当前出现的次数最多的元素，用另一个数字 count 表示该元素出现的次数。遍历所有元素，当前元素与num相同，count ++，否则count --。当count == 0 时， 更新 num 。最后需要再遍历一遍，检查该数字出现次数是否超过⌊ n/2 ⌋。

该方法可以推广到求出现次数超过 ⌊ n/m ⌋ 次的元素。只需要用m个数字表示当前出现最多的数字，用另外m个数字表示他们出现的次数。

代码

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length < 1) {
            return res;
        }
        int[] num = new int[2];
        int[] count = new int[2];
        for (int each : nums) {
            if (each == num[0]) {
                count[0]++;
            } else if (each == num[1]) {
                count[1]++;
            } else if (count[0] == 0) {
                count[0] = 1;
                num[0] = each;
            } else if (count[1] == 0) {
                count[1] = 1;
                num[1] = each;
            } else {
                count[0]--;
                count[1]--;
            }
        }
        count[0] = 0;
        count[1] = 0;
        for (int each : nums) {
            if (each == num[0]) {
                count[0]++;
            } else if (each == num[1]) {
                count[1]++;
            }
        }
        if (count[0] > nums.length / 3) {
            res.add(num[0]);
        }
        if (count[1] > nums.length / 3) {
            res.add(num[1]);
        }
        return res;
    }
}