【LeeCode】229. 多数元素 II

【题目描述】

​​https://leetcode.cn/problems/majority-element-ii/description/​​

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

【示例】

【代码】

package com.company;
import java.util.*;

public class threeSum {
    public static void main(String[] args) {
       int[] arr = {2,2,1,1,1,2,2};  // 2
       int[] arr1 = {1, 2};         // 3
       majorityElement(arr);
       majorityElement(arr1);
    }
    public static List<Integer> majorityElement(int[] nums) {
        int size = nums.length / 3;
        Map<Integer, Integer> map = new HashMap<>(size);

        for(int num: nums){
            // map.merge(num, 1, Integer::sum);
            map.merge(num, 1, (x, y) -> x + y);
        }
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> en : map.entrySet()) {
            if(en.getValue() > size){
                list.add(en.getKey());
            }
        }
        return list;
    }
}

【摩尔投票法思路】

​​点击查看​​