LeetCode137|求众数II

1,问题简述

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

2，示例

示例 1：


输入：[3,2,3]
输出：[3]
示例 2：


输入：nums = [1]
输出：[1]
示例 3：


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


提示：


1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109


 

3，题解思路

使用键值对集合HashMap来做

4，题解程序

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;


public class MajorityElementTest3 {
    public static void main(String[] args) {
        int[] arr = {3, 2, 3};
        List<Integer> list = majorityElement(arr);
        System.out.println("list = " + list);


    }


    public static List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return list;
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer> collect = map.entrySet().stream().filter(x -> x.getValue() > nums.length / 3).map(x -> x.getKey()).collect(Collectors.toList());
        return collect;
    }
}

5，题解程序图片版

6，总结一下

键值对集合我在以往的文章中多次提到了，其实它是一个很常用的知识点，对于开发者来说，其实Map,LinkedHashMap,ConcurrentHashMap,都是一个很常用的，这里只是提到一下，对于你有用就行了。