友链
姚屹晨

leetcode - [229] Majority Element II

2020/05/27

题目描述

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

给一个长度为n的数组，找出其中所有出现频率超过n/3的元素。

举个例子：

Example 1:
Input: [3,2,3]
Output: [3]

Example 2:
Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Update at 2020_0625

重新梳理一下重点：

首先，两个候选人可以随机选择不一样的值，并将两个cnt均初始化为0。

一旦进入循环，则会出现两种情况：

第一种，直接蒙中一个候选人，则cnt++。

否则，将当前元素替换成候选人。

第二点，循环中的所有条件都是互斥的，只能触发一次。

最后，记得判断候选人的出现频率是否大于n / 3。

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        
        List<Integer> ans = new LinkedList<>();
        int len = nums.length;
        if (len == 0) return ans;
        
        int cand1 = 0;
        int cand2 = 1;
        int cnt1  = 0;
        int cnt2  = 0;
        
        for (int i = 0; i < len; i++){
            int cur = nums[i];
            if (cur == cand1){
                cnt1++;
            } else if (cur == cand2){
                cnt2++;
            } else if (cnt1 == 0){
                cand1 = cur;
                cnt1  = 1;
            } else if (cnt2 == 0){
                cand2 = cur;
                cnt2  = 1;
            } else {
                cnt1--;
                cnt2--;
            }
        }
        
        int fre1 = 0;
        int fre2 = 0;
        for (int n: nums){
            if (n == cand1) fre1++;
            if (n == cand2) fre2++;
        }
        
        if (fre1 > len / 3) ans.add(cand1);
        if (fre2 > len / 3 && !ans.contains(cand2)) ans.add(cand2);
        return ans;
    }
}

解法1

使用哈希表实现功能：

实现如下：

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int len = nums.length;
        ArrayList<Integer> ans = new ArrayList<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int n: nums){
            int cur = map.getOrDefault(n, 0) + 1;
            if (cur > len / 3){
                ans.add(n);
            }
            map.put(n, cur);
        }
        return ans.stream().distinct().collect(Collectors.toList());
    }
}

解法2

Thanks @orbuluh

使用Boyer-Moore Majority Vote algorithm算法，思想如下：

首先，假设两个候选人，比如0和1，并分别设置出现次数c1和c2。

然后，遍历数组，如果当前元素与候选人A相等，则c1++，若与候选人B相等，则c2++。

当上面两种情况均不符合，而此时c1 == 0，则将当前元素设置为候选人A，并且c1 = 1，c2同理。

若以上四种情况均不满足，则c1和c2分别减一。

以上只是获取两个候选人的步骤。

然后，分别计算候选人在原始数组中出现的频率，若大于n/3，则转正。

示意图如下：

实现如下：

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        ArrayList<Integer> ans = new ArrayList<>();
        if (nums == null || nums.length == 0) return ans;
        int len = nums.length;

        // Step1: Get two candidate.
        int candidate1 = 0, candidate2 = 1;
        int count1     = 0, count2     = 0;

        for (int n: nums){
            if (n == candidate1){
                count1++;
            } else if (n == candidate2){
                count2++;
            } else if (count1 == 0){
                candidate1 = n;
                count1 = 1;
            } else if (count2 == 0){
                candidate2 = n;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        // Step2: Get the answer use the candidates.
        int[] candidates = {candidate1, candidate2};
        for (int i = 0; i < candidates.length; i++){
            int cur = candidates[i];
            int fre = 0;
            for (int n: nums){
                if (n == cur){
                    fre++;
                }
            }
            if (fre > len / 3){
                ans.add(cur);
            }
        }
        return ans;
    }
}

Enjoy it!


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory