347. Top K Frequent Elements

    xiaoxiao2021-03-26  8

    Given a non-empty array of integers, return the k most frequent elements.

    For example, Given [1,1,1,2,2,3] and k = 2, return [1,2].

    Note: 

    You may assume k is always valid, 1 ≤ k ≤ number of unique elements.Your algorithm's time complexity must be better than O(n log n), where n is the array's size. 这道题用Bucket Sort,新建一个List<Integer>[nums.length + 1],再新建一个hashmap把所有的数和出现的次数存下来,再以出现次数为索引把把数存到相应的 List<Integer>[i]里,在从后向前遍历k个List<Integer>输出。代码如下:

    public class Solution { public List<Integer> topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); List<Integer>[] list = new List[nums.length + 1]; List<Integer> res = new ArrayList<Integer>(); for (int num: nums) { map.put(num, map.getOrDefault(num, 0) + 1); } for (int num: map.keySet()) { if (list[map.get(num)] == null) { list[map.get(num)] = new ArrayList<Integer>(); } list[map.get(num)].add(num); } for (int i = nums.length; res.size() < k && i >= 0; i --) { if (list[i] != null) { res.addAll(list[i]); } } return res; } }

    转载请注明原文地址: https://ju.6miu.com/read-600403.html

    最新回复(0)