Skip to content

Latest commit

 

History

History
116 lines (77 loc) · 3.81 KB

2019-06-08.md

File metadata and controls

116 lines (77 loc) · 3.81 KB
Raw

每日一题 - Top K Frequent Elements

信息卡片

题目描述

Given a non-empty array of integers, return the k most frequent elements.
 
Example 1:
 
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:


Input: nums = [1], k = 1
Output: [1] 
 
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.

简单来说，此题要求找出一个数组中出现次数最多的前K个数。

参考答案

以下参考答案均是以Java语言实现，不过对其他语言，思路都是相同的。

题目要求时间复杂度必须比O(n log n)要好，第一种解法的复杂度是O(n)，第二种解法由于使用了优先队列，时间复杂度要比O(n)略差，但仍然能AC，所以优先推荐第一种使用HashMap + 桶的解法。

解法I：HashMap + 桶

  • 用HashMap统计所有元素的出现频率
  • 将统计结果按照出现次数把对应元素放入以出现次数为基础的桶中
  • 按照从后往前的顺序从桶中取前K个元素便是答案

参考代码

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
      if (nums == null || nums.length == 0 || k <= 0) return Collections.emptyList();

      Map<Integer, Integer> statisticMap = new HashMap<>();

      for (int i : nums) statisticMap.put(i, statisticMap.getOrDefault(i, 0) + 1);

      // 记录出现次数和对应元素的桶
      List<Integer>[] bucket = new List[nums.length + 1];

      for (int i : statisticMap.keySet()) {
        int frequency = statisticMap.get(i);

        if (bucket[frequency] == null) bucket[frequency] = new ArrayList<Integer>();

        bucket[frequency].add(i);
      }

      List<Integer> result = new ArrayList<>();

      for (int i = bucket.length - 1; i >= 0; i--) {
        if (bucket[i] == null) continue;
        
        if (result.size() >= k) break;

        result.addAll(bucket[i]);
      }

      return result;
   }
}

解法II：HashMap + PriorityQueue

思路大致和前面相同，不过是将出现频率的排序交给了优先队列而已，在使用优先队列的时候给其提供了一个比较器，该比较器会对加入的元素自动排序，最后选择优先队列的前K的元素返回即可。

参考代码

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
      if (nums == null || nums.length == 0 || k <= 0) return Collections.emptyList();
      
      Map<Integer, Integer> map = new HashMap<>();
      
      for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
      
      // 优先队列
      PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
        @Override
        public int compare(Map.Entry<Integer, Integer> e1, Map.Entry<Integer, Integer> e2) {
          return e2.getValue() - e1.getValue(); // 确保出现次数多的数排列在队列的前面
       }
      });
      
      for (Map.Entry<Integer, Integer> entry : map.entrySet()) pq.add(entry);
      
      int i = 1;
      List<Integer> result = new ArrayList<>();
      
      while (i++ <= k) result.add(pq.poll().getKey());
      
      return result;
   }
}

其他优秀解答

本题基本上好的解答就是上面的两种办法，为了格式和其他同学的PR尽量一致，我在编写此PR的时候删去了我解题时写下的详细注释，需要看详细注释的同学请移步此处的第347题