题目描述

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

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

示例 1:

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

示例 2:

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

https://leetcode-cn.com/problems/majority-element-ii/

解法1

使用Map统计每种数字出现的频率,当发现元素e出现当频率大于⌊ n/3 ⌋时,将其加入到结果列表中,当扫描完数组后返回结果列表。时间复杂度与空间复杂度均为O(n)。

解法2

解法2使用169题的方法,也就是Boyer–Moore majority vote algorithm。我们首先分析下,在数组中出现频率超过⌊ n/3 ⌋最多能有几种元素。容易想到,最多我们只能找到两个元素,它的出现频率大于⌊ n/3 ⌋(如果存在3个,则3个元素频率均为n/3)。

我们还是使用Boyer-Moore算法,创建4个变量counter1、counter2、num1、num2。遍历每个元素e,如果counter1为0,则将元素e赋给num1,且将counter1置为1;如果counter2为0,则将元素e赋给num2,且将counter2置为1;如果e == num1,则counter1自增1;如果e == num2,则counter2自增1;否则(e!=num1且e!=num2),counter1与counter2自减1.

全部代码如下,需要注意的是需要将判断e == num1/2放在if(counter1/2 == 0)之前,否则出现两个相同的元素,将会分别使用counter1与counter2统计,逻辑就不正确了。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int num1 = 0, num2 = 0;
        int counter1 = 0, counter2 = 0;
        List<Integer> res = new ArrayList<>();

        for (int e : nums) {
            if (e == num1) {
                counter1++;
            } else if (e == num2) {
                counter2++;
            } else if (counter1 == 0) { // counter分支要放到if e == num1,2之后,
                                        // 否则遇到两个连续的数,会分别利用counter1,counter2统计
                num1 = e;
                counter1 = 1;
            } else if (counter2 == 0) {
                num2 = e;
                counter2 = 1;
            } else {
                counter1--;
                counter2--;
            }
        }

        // 该算法不保证遍历后,num1与num2就是出现频率大于n/3的元素
        // 需要再一次扫描来确定
        counter1 = 0;
        counter2 = 0;

        for (int e : nums) {
            if (e == num1)
                counter1++;
            else if (e == num2)
                counter2++;
        }

        if (counter1 > nums.length / 3)
            res.add(num1);

        if (counter2 > nums.length / 3)
            res.add(num2);

        return res;
    }
}

Leave a Reply

Your email address will not be published. Required fields are marked *