使用Java8 Stream来完成力扣 347. 前 K 个高频元素

题目及思路

给一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

例如：

输入: nums = [1,1,1,2,2,3], k = 2

输出: [1,2]

思路很简单：

将存到Map中，将map按value倒序排序，输出前k个返回。

经典做法

下面是根据上面的思路实现的代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if(k == 0 || nums.length == 0){
            int tmp[] = {};
            return tmp;
        }
        //创建返回的res数组
        int res[] = new int[k];
        //创建map
        Map<Integer, Integer> map = new HashMap<>();
        //将nums数组中元素和元素出现的次数保存到map中
        for (int num : nums) {
            if(map.containsKey(num)) {
                map.put(num, map.get(num)+1);
            } else {
                map.put(num, 0);
            }
        }
        //创建map.entrySet()的list用于排序
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        //按map的值倒序排序
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
        //取出前k个放到res中
        for (int i = 0; i < k; i++) {
            res[i] = list.get(i).getKey();
        }
        return res;
    }
}

使用Stream

使用Stream实现的代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        return Arrays.stream(nums) // IntStream
                .boxed() // Stream<Integer>
                .collect(Collectors.toMap(key -> key, value -> 1, Integer::sum)) // Map<Integer, Integer>
                .entrySet() // Set<Map<K, V>.Entry<Integer, Integer>>
                .stream() // Stream<Map<K, V>.Entry<Integer, Integer>>
                .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
                .map(Map.Entry::getKey) // Stream<Integer>
                .limit(k)
                .mapToInt(i -> i) //IntStream
                .toArray();
    }
}

是不是非常的简洁明了？下面对代码做一下必要解释

• 为了将int[]转为流，使用了Arrays.stream(nums)

• 需要注意的是，普通的流总是包装类，但这里直接得到了IntStream，为了后面封装为Map<Integer, Integer>，所以需要使用boxed()将IntStream转为Stream<Integer>

• collect将Stream收集到一个Map

• Collectors.toMap的三个参数分别是，收集到Map的key，value当遇到重复key时的处理方法；

• 3-5行的代码等价于下面

  • Map<Integer, Integer> map = new HashMap<>();
    Arrays.stream(nums).forEach(num -> {
        map.put(num, map.getOrDefault(num, 0) + 1);
    });
    

• 为了从map中再次获得流，我们使用代码先得到map的set在获得流。代码对应entryset()和stream()

• 获得流之后需要根据value进行倒序排序，使用sorted()，其传入的参数是一个比较器

• 排序之后映射使用map()将Stream<Map<K, V>.Entry<Integer, Integer>>映射为Stream<Integer>

• 我们只需要前k个，所以用limit(k)

• 使用mapToInt(i -> i)进行拆包，得到IntStream

• toArray()转换为数组并返回。

总结

Java8 Stream在处理集合方面有着很大的优势：

• 逻辑清晰
• 代码简洁
• ……

但我刚接触，使用起来不是很熟悉，还需要再多练习。

参考资料

null