【Day 20 】2021-09-29 - 347. 前 K 个高频元素

[azl397985856]

347. 前 K 个高频元素

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/top-k-frequent-elements/

前置知识

• 哈希表
• 堆排序
• 快速选择

  题目描述

  
  给定一个非空的整数数组，返回其中出现频率前  k  高的元素。
  示例 1:

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

示例 2:

输入: nums = [1], k = 1 输出: [1]

提示：

• 你可以假设给定的  k  总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n  是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/top-k-frequent-elements 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[BlueRui]

Problem 347. Top K Frequent Elements

Algorithm

• Iterate over the array and use a map to keep track of counts of each value.
• Use a priority queue to maintain k map entries with the highest frequency.

Complexity

• Time Complexity: Creating map takes O(N) time. Iterating entries to create priority queue takes O(Nlogk) time. Total is O(Nlogk).
• Space Complexity: O(N).

Code

Language: Java

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> counter = new HashMap<>();
    PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            Map.Entry.<Integer, Integer>comparingByValue());

    for (int num : nums) {
        counter.putIfAbsent(num, 0);
        counter.put(num, counter.get(num) + 1);
    }
    for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {
        pq.offer(entry);
        if (pq.size() > k) {
            pq.poll();
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = pq.poll().getKey();
    }
    return result;
}

[itsjacob]

Intuition

• Top-k problems can be solved by heap by maintaining a heap of size k, or by quick select
• This problem needs an extra step to count the frequencies of each number first, so a hashtable is needed

Implementation

class Solution
{
public:
  vector<int> topKFrequent(vector<int> &nums, int k)
  {
    // The top k problems are solved by heaps, we need minimum heap to store most frequent elements
  std:
    vector<int> res;
    // pair<count, n>
    std::vector<std::pair<int, int>> aVec;
    auto comp = [](std::pair<int, int> &p1, std::pair<int, int> &p2) { return p1.second > p2.second; };

    // First pass to count the frequencies of nums
    // key,val = num, count
    std::unordered_map<int, int> aMap;
    for (auto const &n : nums) {
      if (aMap.count(n) > 0) {
        aMap[n]++;
      } else {
        aMap.emplace(n, 1);
      }
    }

    // All std::make_heap, std::push_heap, std::push_heap need to use comparator to work with min heap
    // min heap of size k to store the most k frequent elements
    for (auto const &m : aMap) {
      if (aVec.size() < k) {
        aVec.emplace_back(std::move(m));
        if (aVec.size() == k) {
          std::make_heap(aVec.begin(), aVec.end(), comp);
        }
        continue;
      }
      if (aVec.front().second < m.second) {
        // Remove the least frequent element from the heap
        std::pop_heap(aVec.begin(), aVec.end(), comp);
        aVec.pop_back();

        aVec.emplace_back(std::move(m));
        std::push_heap(aVec.begin(), aVec.end(), comp);
      }
    }

    for (auto const &p : aVec) {
      res.push_back(p.first);
    }

    return res;
  }
};

Complexity

• Time complexity: O(NlogK), logK for maintaining the heap property when doing pop and push
• Space complexity: O(N)

[Joyce94]

思路

统计每个元素出现的次数 遍历map，用最小堆保存频率最大的k个元素

代码

class Solution {
    // HashMap<Integer, Integer> map;
    // static Comparator<Integer> cmp = new Comparator<>(){
    //     public int compare(Integer o1, Integer o2){
    //         return map.get(o1)-map.get(o1);
    //     }
    // };
    public List<Integer> topKFrequent(int[] nums, int k) {
        // 统计每个元素出现的次数
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        // 遍历map，用最小堆保存频率最大的k个元素
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<>(){
            @Override
            public int compare(Integer o1, Integer o2){
                return map.get(o1)-map.get(o2);
            }
        });
        for (Integer key: map.keySet()){
            if (queue.size()<k){
                queue.add(key);
            }else{
                queue.add(key);
                queue.poll();
            }
        }
        List<Integer> res = new ArrayList<>();
        while (queue.size()>0){
            res.add(queue.poll());
        }
        return res;
    }
}

[zhy3213]

思路

哈希表+小顶堆（优先队列）

代码

    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import queue
        times=dict()
        for i in nums:
            if i in times:
                times[i]+=1
            else:
                times[i]=1
        resq=queue.PriorityQueue()
        for i in times:
            if k > (resq.qsize()) :
                resq.put((times[i],i))
            else:
                if resq.queue[0][0]<times[i]:
                    resq.get()
                    resq.put((times[i],i))
        res=[]
        while not resq.empty():
            res.append(resq.get()[1])
        return res

时间O(NlogK) 空间O(N)

[AgathaWang]

hash table + python暴力法排序

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # hashtb = collections.defaultdict(int)
        # for num in nums:
        #     hashtb[num] += 1
        hashtb = collections.Counter(nums)
        # print(hashtb)
        return sorted(hashtb,key = lambda x:hashtb[x],reverse=True)[:k]

[JinMing-Gu]

class Solution {
public:
    static bool cmp(pair<int, int>& m, pair<int, int>& n) {
        return m.second > n.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> occurrences;
        for (auto& v : nums) {
            occurrences[v]++;
        }

        // pair 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for (auto& [num, count] : occurrences) {
            if (q.size() == k) {
                if (q.top().second < count) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }
        vector<int> ret;
        while (!q.empty()) {
            ret.emplace_back(q.top().first);
            q.pop();
        }
        return ret;
    }
};

[james20141606]

Day 20: 347. Top K Frequent Elements (hashtable, quick select, heap, divide and conquer, bucket sort)

• Problem Link

  • 347. Top K Frequent Elements

• Ideas

  • Use hash table and bucket: Time: O(N), and Space: O(N)
  • Use hash table and heap: Time: O(NlogK), Space: O(N)
  • Use hash table and sort: Time: O(NlogN), Space: O(N)

• Complexity: hash table and bucket

  • Time: O(N)
  • Space: O(N)

• Code

#sorted, key could be used to decide which is used to sort, could pass a function
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = Counter(nums)
        return sorted(dic.keys(),key = lambda x:-dic[x])[:k]

#use bucket, and chain
class Solution:
    def topKFrequent(self, nums, k):
        bucket = [[] for _ in range(len(nums) + 1)]
        Count = Counter(nums).items()  
        for num, freq in Count: bucket[freq].append(num)
        #chain used to combine multiple iterators
        print (bucket, list(chain(*bucket)))
        flat_list = list(chain(*bucket))
        return flat_list[::-1][:k]

#detailed of the above solution
import collections
class Solution:
    def topKFrequent(self, nums, k):
        bucket = [[] for _ in range(len(nums))]
        count = collections.defaultdict(int) #int,set,string,list...
        for i in nums:
            count[i] += 1
        for key,value in count.items():
            bucket[value-1].append(key)
        flatten_list = []
        for i in bucket:
            flatten_list +=i
        return flatten_list[::-1][:k]

#use counter and heap
import heapq
from collections import Counter
class Solution:
    def topKFrequent(self, nums, k):
        res = []
        dic = Counter(nums)
        max_heap = [(-val, key) for key, val in dic.items()]
        heapq.heapify(max_heap)
        for i in range(k):
            res.append(heapq.heappop(max_heap)[1])
        return res

# or use heapq.nsmallest
import heapq
from collections import Counter
class Solution:
    def topKFrequent(self, nums, k):
        res = []
        dic = Counter(nums)
        max_heap = [(-val, key) for key, val in dic.items()]
        maximum = heapq.nsmallest(k, max_heap)
        return  [i[1] for i in maximum]

• other resources:

[ivalkshfoeif]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequency = new HashMap<>();
        for (int num : nums){
            frequency.put(num, frequency.getOrDefault(num,0) + 1);
        }

        List<Integer>[] buckets = new ArrayList[nums.length + 1];
        for (int key : frequency.keySet()){
            int value = frequency.get(key);
            if (buckets[value] == null){
                buckets[value] = new ArrayList();
            }
            buckets[value].add(key);
        }
        List<Integer> topK = new ArrayList<>();
        for (int i = nums.length; i >=0 && topK.size() < k; i--){
            if (buckets[i] == null){
                continue;
            }

            if (buckets[i].size() < (k - topK.size())){
                topK.addAll(buckets[i]);
            } else {
                topK.addAll(buckets[i].subList(0, k - topK.size()));
            }

        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++){
            ans[i] = topK.get(i);
        }

        return ans;

    }
}

桶排序，遍历常数次 O（N）， 但是需要确定桶的数量，如果桶数目数量级较高，那么时间复杂度会取决于桶的数量，此时快排的时间复杂度依旧取决于实际元素的数量

[xjlgod]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> num2Count = new HashMap<>();
        Map<Integer, List<Integer>> count2Num = new HashMap<>();
        int len = nums.length;
        int[] res = new int[k];
        for (int i = 0; i < len; i++) {
            num2Count.put(nums[i], num2Count.getOrDefault(nums[i], 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : num2Count.entrySet()) {
            int num = entry.getKey();
            int count = entry.getValue();
            if (!count2Num.containsKey(count)) {
                count2Num.put(count, new ArrayList<>());
            }
            List<Integer> list = count2Num.get(count);
            list.add(num);
        }
        List<Map.Entry<Integer, List<Integer>>> list = new ArrayList<>(count2Num.entrySet());
        Collections.sort(list, (a, b) -> b.getKey() - a.getKey());
        int index = 0;
        for (Map.Entry<Integer, List<Integer>> entry : list) {
            if (index == k) {
                break;
            }
            int count = entry.getKey();
            for (int num : entry.getValue()) {
                if (index == k) {
                    break;
                }
                res[index] = num;
                index++;
            }
        }
        return res;
    }
}

[chaggle]

---

title: "Day 20 347. 前 K 个高频元素" date: 2021-09-29T10:22:10+08:00 tags: ["Leetcode", "c++", "priority_queue","unordered_map"] categories: ["algorithm"] draft: true

---

347. 前 K 个高频元素

题目

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

示例 1:

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

示例 2:

输入: nums = [1], k = 1
输出: [1]
 
提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
 

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

题目思路

• 1、典型的大顶堆问题，可以建立一个无序的unordered_map保存键值对，而后在建立一个priority_queue，因为C++中priority_queue默认是大顶堆的建立，故将unordered_map中的序列对{k,v}序列改为{v,k}即可保存在priority_queue中。然后输出前n个键值对的v值即可。
• 2、进阶版可以手写一个堆替换priority_queue，等以后有时间再来补坑。

代码块。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int n) {
        unordered_map<int, int> up;
        for(auto i : nums) up[i]++;
        priority_queue<pair<int, int>> p;
        for(auto it = up.begin(); it != up.end(); it++) p.push({it -> second, it -> first});
        vector<int> ans;
        while(n--) 
        {
            ans.push_back(p.top().second);
            p.pop();
        }
        return ans;
    }
};

复杂度

• 时间复杂度：O(nlogn)

• 空间复杂度：O(n)

[ningli12]

思路

• 遍历数组 用hashmap记录每个数出现的次数
• 遍历map，用最小堆保存频率最大的k个元素

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        if(nums.length == 0) return new int[]{};

        Map<Integer, Integer> map = new HashMap<>();
        for(int n: nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });
        for (Integer key : map.keySet()) {
            pq.add(key);
            if (pq.size() > k) {
                pq.poll();
            }
        }

        List<Integer> list = new ArrayList<>();
        while (!pq.isEmpty()) {
            list.add(pq.remove());
        }

        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

complexity

Time : O(Nlogk) Space : O(N+k)

[akxuan]

hashtable 用 value 排序而已

时 O(NlogN) 空是 O(N)

class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """

        count = {}
        for i in nums:
            if i in count:
                count[i] +=1
            else:
                count[i] = 1

        items = count.keys()        
        items.sort( key = lambda x:count[x], reverse =True )

        return items[:k]

[skinnyh]

Note

• Use dict to count each number's frequency. Then maintain a min heap of size K. Adding the tuple of (frequency, num) to the heap and the final numbers in the heap are the result.

Solution

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = {}
        for n in nums:
            d[n] = d.get(n, 0) + 1
        q = [] # min heap
        for n in d:
            if len(q) < k:
                heappush(q, (d[n], n))
            elif q[0][0] < d[n]:
                heapreplace(q, (d[n], n))
        return [n[1] for n in q]

Time complexity: O(NlogK)

Space complexity: O(N+K)

[iambigchen]

思路

定义map，遍历nums，key为nums的值，value为出现的频率。之后再对value进行排序

代码

var topKFrequent = function(nums, k) {
    let map = {}
    for (let index = 0; index < nums.length; index++) {
        const e = nums[index];
        if (!map[e]) {
            map[e] = 1
        } else {
            map[e] += 1
        }
    }
    let keys = Object.keys(map)
    keys.sort((a, b) => map[b] - map[a])
    return keys.slice(0, k)
};

复杂度

时间复杂度 O(logN)

空间复杂度 O(N)

[carterrr]

class Solution {

public static void main(String[] args) {
    Solution solution = new Solution();
    int[] ints = solution.topKFrequentFastSort(new int[]{1, 1, 1, 2, 2, 3}, 2);
    System.out.println();
}
public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> frequency = new HashMap<>();
    for(int num : nums) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }
    //按照频率来的小顶堆  PriorityQueue无法实现定长  需要自行判断
    PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
    for(Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
        if(queue.size() == k) {
            if(queue.peek()[1] >= entry.getValue()) {
                continue;
            }
            queue.poll();
        }
        queue.offer(new int[]{entry.getKey(), entry.getValue()});
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) {
        res[i] = queue.poll()[0];
    }
    return res;
}

/**
 * 快排方式找k位置 注意不是完全排序 只找前大后小的第k位置的方法
 */
public int[] topKFrequentFastSort(int[] nums, int k) {
    Map<Integer, Integer> frequency = new HashMap<>(nums.length);
    for(int num : nums) {
        frequency.put(num, frequency.getOrDefault(num, 0) + 1);
    }
    int[][] fArr = new int[frequency.size()][2];
    int i = 0;
    for(Map.Entry<Integer, Integer> entry : frequency.entrySet()) {
        fArr[i][0] = entry.getKey();
        fArr[i][1] = entry.getValue();
        i ++;
    }

    return findTopK(fArr, k, 0, fArr.length - 1);
}

// 题中快排只考虑找pivot基准位置 并不是完全的快排
private int[] findTopK(int[][] arr, int k, int low, int high) {
    int pivot = low + (int) (Math.random() * (high - low + 1)); // 注意  这里要加上起始坐标low
    swap(arr, pivot, low); // 交换low和随机下标
    int i = low, base = arr[low][1]; // 以low的frequency为基准  进行倒序快排
    for (int j = low + 1; j <= high; j++) {  // 因为 low、high 都是具体坐标  因此  j可以等于high
        if(arr[j][1] > base ) {
            swap(arr,  ++ i, j); // 交换 i 的下一个元素 和j 保证从low的下一个开始 都是大于base的
        }
    }
    swap(arr, low, i);
    if(i == k - 1) {
        int[] topK = new int[k];
        for(int f = 0; f < k; f++) {
            topK[f] = arr[f][0];
        }
        return topK;
    } else if( i > k - 1) {
        return findTopK(arr, k, low, i - 1 );
    } else {
        return findTopK(arr, k, i + 1, high );
    }

}

/**
 * 二维数组交换
 */
private void swap(int[][] arr, int pivot, int low) {
    if(pivot == low) return;
    int[] tmp = arr[pivot];
    arr[pivot] = arr[low];
    arr[low] = tmp;
}

}

[laurallalala]

代码

  d = collections.defaultdict(int)
        for num in nums:
            d[num] += 1
        heap = []
        for num in d:
            heapq.heappush(heap, (d[num], num))
            if len(heap) > k:
                heapq.heappop(heap)
        return [num for ct, num in heap]

复杂度

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

[lxy030988]

思路

• 遍历数组,把每个数据暂存到 map 中,数据存在 值+1
• 排序 map

代码 js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const map = new Map()
  for (let i = 0; i < nums.length; i++) {
    if (map.has(nums[i])) {
      map.set(nums[i], map.get(nums[i]) + 1)
    } else {
      map.set(nums[i], 1)
    }
  }
  const res = Array.from(map.entries())
    .sort((a, b) => b[1] - a[1])
    .slice(0, k)
    .map((item) => item[0])
  // console.log('map', map, res)
  return res
}

复杂度分析

• 时间复杂度：O(n*logn) sort 复杂度
• 空间复杂度：O(n)

[chun1hao]

var topKFrequent = function(nums, k) {
  let map = new Map()
  for(let i of nums){
    let num = map.get(i) || 0
    map.set(i, ++num)
  }
  let arr = Array.from(map.entries())
  let len = arr.length
  let result = topK(arr, start=0, end=len-1, len-k)
  return result.map(i=> i[0])
};
function topK(arr, start, end, k){
  if(start<end){
    let povit = arr[end][1]
    let pos = start - 1
    for(let i=start;i<=end;i++){
      if(arr[i][1]<=povit){
        pos++
        [arr[i], arr[pos]] = [arr[pos], arr[i]]
      }
    }
    if(pos<k){
      topK(arr, pos+1, end, k)
    }else if(pos==k){
      return arr.slice(pos)
    }else{
      topK(arr, start, pos-1, k)
    }
  }
  return arr.slice(k)
}

[biancaone]

思路 🏷️

用哈希表记录下元素及对应出现次数

---

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        mapping = {}
        for i in nums:
            if i in mapping:
                mapping[i] +=1
            else:
                mapping[i] = 1

        items = list(mapping.keys())        
        items.sort(key = lambda x:mapping[x], reverse=True)

        return items[:k]

[watchpoints]

/*
 * @lc app=leetcode.cn id=347 lang=cpp
 *
 * [347] 前 K 个高频元素
 */

// @lc code=start
class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {

        //01 统计每个元素出现次数 time:o（n logn）
        map<int, int> counts;
        for (auto key : nums)
        {
            counts[key]++; //map key是有序的。但是value无法排序。 需要办法解决！
        }

        //02 为什么是小heap space:o(k)
        //假如 知道一个元素元素出现的频率，如果判断是否k个大，
        //只要和假设前面k个最小的一个比较就可以

        /**定义一下比较函数*/
        auto cmp = [](const pair<int, int> &a, const pair<int, int> &b) { return a.second > b.second; };
        // 定义优先级队列
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> minHeap(cmp);

        //03 求top k time:o（n logn）
        //https://www.cnblogs.com/developing/articles/10890903.htmlC++11新特性——for遍历
        for (auto &key : counts)
        {
            if (minHeap.size() < k)
            {
                minHeap.emplace(key.first, key.second);
            }
            else if (key.second > minHeap.top().second)
            {
                minHeap.pop();
                minHeap.emplace(key.first, key.second);
            }
        }

        //04 打印
        vector<int> ret;
        while (!minHeap.empty())
        {
            int temp = minHeap.top().first;
            minHeap.pop();
            ret.push_back(temp);
        }

        return ret;
    }
};

[jz1433]

思路

use hashmap to store {val:freq}, then sort by frequency and output top k

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        hashmap = {}
        for val in nums:
            if val in hashmap:
                hashmap[val] += 1
            else:
                hashmap[val] = 1
        valByFreq = [val for val, freq in sorted(hashmap.items(), key=lambda item: item[1], reverse=True)]
        return valByFreq[:k]

复杂度

Time: O(nlogn) //bcz of sort Space: O(n)

[Laurence-try]

思路

First, we can use Hash table to store the nums with their frequency, where key is the number and value is its frequency. Then, we can use priority queue (heapq) in python to sort a tuple (freq, num). However, we need to notice that we can limit the length of heapq to k while keeping pushing the tuple (bucket sort). While finishing pushing, we can have the k top the most frequent numer tuple.

代码

使用语言：Python3

from heapq import heappush, heappop
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        res = []
        res_freq = []
        for num in nums:
            if num in dic.keys():
                dic[num] = dic[num] + 1
            else:
                dic[num] = 1
        h = []
        for key in dic:
            heappush(h, (dic[key], key))
            if len(h) > k:
                heappop(h)
        res = []
        while h:
            _, num = heappop(h)
            res.append(num)
        return res

复杂度分析 时间复杂度：O(nlogn) 空间复杂度：O(n)

[HouHao1998]

思想

先用哈希表记录每一个元素重复的次数

代码

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map= new HashMap<>();
        for (int num :nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(m -> m[1]));
        //循环遍历整个map
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }

复杂度

时间复杂度：O(nlogn) 空间复杂度：O(n)

[lilixikun]

思路

用哈希表记录每一个元素出现的次数、然后进行排序、返回前K个元素

代码

function topKFrequent(nums, k) {
  let map = {}
  for (const num of nums) {
    map[num] ? map[num]++ : map[num] = 1
  }
  const res = Object.keys(map).sort((a, b) => map[b] - map[a]).slice(0, k)
  return res
}

[JK1452470209]

思路

用hash表存储数据计数数量，并将hash表中的值进行分桶，让次数一样的分在同一个桶中，然后只要倒序把桶中的数转进返回数据即可。

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        List<Integer> res = new LinkedList<>();
        List<Integer>[] bucket = new List[nums.length + 1];
        Map<Integer, Integer> counter = new HashMap<>();

        for (int num: nums){
            counter.put(num, counter.getOrDefault(num, 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry: counter.entrySet()) {
            int val = entry.getValue();
            if (bucket[val] == null){
                bucket[val] = new LinkedList<>();
            }
            bucket[val].add(entry.getKey());
        }

        int kNum = 0;
        for (int i = bucket.length - 1; i >= 0; i--)
            if (bucket[i] != null)
                for (int elem: bucket[i]){
                    res.add(elem);
                    kNum++;
                }
        int[] ret = new int[k];
        for (int i = 0; i < ret.length; i++){
            ret[i] = res.get(i);
        }

        return ret;
    }
}

复杂度

时间复杂度：O(N)，N为数组的长度

空间复杂度：O(N)，N为数组的长度

[ZJP1483469269]

class Solution { public int[] topKFrequent(int[] nums, int k) { HashMap<Integer,Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++){ map.put(nums[i],map.getOrDefault(nums[i],0)+1); } return topkMax(map,k); } public static int[] topkMax(HashMap<Integer,Integer> map,int k){ PriorityQueue<int[]> pd = new PriorityQueue<int[]>(new Comparator<int[]>() { public int compare(int[] m, int[] n) { return m[1] - n[1]; } });

    int i=0;
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

        int key = entry.getKey(),val = entry.getValue();
        if(i<k){
            pd.offer(new int[]{key,val});
        }else if(val>pd.peek()[1]){
            pd.poll();
            pd.offer(new int[]{key,val});
        }
        i++;
    }
    int[] ans =new int[k];
    for(int j=0;j<k;j++){
        ans[j] = pd.poll()[0];
    }
    return ans;

}

}

[15691894985]

day 20 347. 前 K 个高频元素

https://leetcode-cn.com/problems/top-k-frequent-elements/

思路：

• 统计数组中，数字出现的频率

• 根据频率排序，取前k个，排序可以按照堆排序、快速选择排序各种排序方法

哈希表+堆

    class Solution:
        def topKFrequent(self, nums: List[int], k: int) -> List[int]:
            d = {}
            #1.构造hashmap 记录出现频率
            for i in nums:
                d[i]  = d.get(i, 0) +1  #频率

        # 最小堆排序 :最上面的最小把大于k的弹出
            heap1 = []
            for i in d:
                heapq.heappush(heap1,(d[i],i))
                if len(heap1) > k:
                    heapq.heappop(heap1)

            return [i[1] for i in heap1]

复杂度分析：

时间复杂度：可能有O(N)个频率出现，因此总复杂度为O(N*logN)

空间复杂度：O(N)堆所用的空间

[last-Battle]

思路

关键点

• 先用map保存，然后用priority_queue

代码

• 语言支持：C++

C++ Code:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> m;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        vector<int> res;
        for (auto a : nums) {
            ++m[a];
        }

        for (auto& [key, val] : m) {
            q.push(pair<int, int>(val, key));
            if (q.size() > k) {
                q.pop();
            }
        }

        while (!q.empty()) {
            res.emplace_back(q.top().second);
            q.pop();
        }
        return res;
    }
};

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[chenming-cao]

解题思路

方法一：哈希表+桶排序。哈希表储存数字和对应出现次数。从最后一个桶开始往前遍历取k个元素。

方法二：哈希表+堆排序。哈希表储存数字和对应出现次数。建立一个容量为k的最小堆。遍历哈希表，将表中元素以Pair形式存入最小堆中。当堆的容量达到k时，如果遇到大于堆顶的Pair，则取出堆顶Pair，将新Pair放入堆中，否则跳过此Pair。最后返回堆中对应的k个数字即可。

代码

方法一：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] bucket = new List[nums.length + 1]; // from 0 to nums.length
        LinkedList<Integer> res = new LinkedList<>(); // specify to use linked list instead of general list

        for (int num: map.keySet()) {
            int count = map.get(num);
            if (bucket[count] == null) {
                bucket[count] = new LinkedList<Integer>();
            }
            bucket[count].add(num);
        }

        for (int i = nums.length; i >= 0; i--) {
            if (bucket[i] != null) {
                for (int num: bucket[i]) {
                    res.add(num);
                }
            }
        }

        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = res.removeFirst();
        }
        return ans;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为数组长度
• 空间复杂度：O(n)，n为数组长度

方法二：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num: nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Pair<Integer, Integer>> heap = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() {
            public int compare(Pair<Integer, Integer> p1, Pair<Integer, Integer> p2)
            {
                return p1.getValue() - p2.getValue();
            }
        });

        for (int num: map.keySet()) {
            int count = map.get(num);
            if (heap.size() < k) {
                heap.offer(new Pair<>(num, count));
            }
            else {
                if (heap.peek().getValue() < count) {
                    heap.poll();
                    heap.offer(new Pair<>(num, count));
                }
            }
        }

        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = heap.poll().getKey();
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(nlogk)，n为数组长度，k为堆的容量
• 空间复杂度：O(n)，n为数组长度

[benngfour]

思路

1. use hash table to get the frequency of each number
2. use Set to create an array with non-repeat number from nums array
3. sort the array by the hash value, then slice to k.

語言

JavaScript

Code Solution

var topKFrequent = function(nums, k) {
    let hash = {};
    for(const num of nums) {
        if (!hash[num]) {
            hash[num] = 1
        } else {
            hash[num] += 1;
        }
    }
    const uniqeNums = [...new Set(nums)];
    uniqeNums.sort((a,b) => hash[b] - hash[a])
    return uniqeNums.slice(0, k);
};

複雜度分析

• 時間複雜度 O(NlogN)
• 空間複雜度 O(N)

[xieyj17]

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dic = {}
        for n in nums:
            if n not in dic:
                dic[n] = 1
            else:
                dic[n] += 1

        if len(dic) == k:
            return list(dic.keys())

        keys = list(dic.keys())
        vals = list(dic.values())
        nvals = [-v for v in vals]
        heapq.heapify(nvals)
        res = []
        for i in range(k):
            c = heapq.heappop(nvals)
            ti = vals.index(-c)
            tk = keys[ti]
            res.append(tk)
            vals.remove(-c)
            keys.remove(tk)
        return res

用hash map 和 heap 写了一个答案

Time: O(NlogN)

Space: O(N)

[JLin-data]

from collections import Counter
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]: 
        if k == len(nums):
            return nums
        count = Counter(nums)   
        return heapq.nlargest(k, count.keys(), key=count.get) 

[siyuelee]

暴力解法：hashmap存频率，排序取前k。。周末再看看优化。。

class Solution(object):
    def topKFrequent(self, nums, k):

        hashmap = dict()
        for n in nums:
            if n not in hashmap:
                hashmap[n] = 1
            if n in hashmap:
                hashmap[n] += 1

        items = hashmap.keys()        
        items.sort( key = lambda x:hashmap[x], reverse =True )

        return items[:k]   

T: nlogn S: n

[watermelonDrip]

经典top k

class Solution:
    import heapq
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dict_freq = dict()
        for i in range(len(nums)):
            dict_freq[nums[i]] = dict_freq.get(nums[i],0) + 1

        heap = list()
        for val, freq in dict_freq.items():
            heappush(heap,(freq,val))
            if len(heap) > k:
                heappop(heap)

        res = list()
        for freq, val in heap:
            res.append(val)
        return res

Space: O(N) Time: O(N+MlogK+ K) (N: len(nums) , M: len(dict), K: len(heap)) N <= M<=K

[shixinlovey1314]

Title:347. Top K Frequent Elements

Question Reference LeetCode

Solution

Use hashmap to count the frequncy. Then use quick select to find the top K frequent numbers.

Code

class Solution {
public:

    void swap(pair<int, int>& x, pair<int, int>& y) {
        int a = x.first;
        int b = x.second;

        x.first = y.first;
        x.second = y.second;

        y.first = a;
        y.second = b;
    }

    int partition(vector<pair<int, int>>& arr, int s, int e, int k) {
        int store_index = s;
        swap(arr[s], arr[e]);

        // Sort based on frequency descending.
        for (int i = s; i < e; i++) {
            if (arr[i].first > arr[e].first)
                swap(arr[store_index++], arr[i]);
        }

        swap (arr[store_index], arr[e]);

        return store_index;
    }

    void quickSelect(vector<pair<int, int>>& arr, int s, int e, int k) {
        if (arr.size() <= k)
            return;

        int index = partition(arr, s, e, k);

        if (index == k)
            return;
        else if (index < k) {
            quickSelect(arr, index + 1, e, k);
        } else {
            quickSelect(arr, s, index - 1, k);
        }
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        std::map<int, int> counter;

        // Count frequency.
        for (int v : nums) {
            counter[v]++;
        }

        // Move <num, frequency> pair into vector;
        vector<pair<int, int>> analyzer;
        for (auto it = counter.begin(); it != counter.end(); it++) {
            analyzer.push_back(make_pair(it->second, it->first));
        }

        // quick select top k based on frequency.
        quickSelect(analyzer, 0, analyzer.size() - 1, k);

        // fill up result.
        vector<int> result;
        for (int i = 0; i < analyzer.size() && i < k; i++) {
            result.push_back(analyzer[i].second);
        }

        return result;
    }
};

Complexity

Time Complexity and Explanation

O(n), we need to vistis each number once. QuickSelect to find top K only take O(logn), so the total time complexity is O(n)

Space Complexity and Explanation

O(n), used by the hashmap and vector.

[XinnXuu]

347. Top K Frequent Elements

Medium

---

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

 

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

 

Constraints:

• 1 <= nums.length <= 105
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

 

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

### 思路 用哈希表存储，键为元素，键值为频次。维护一个以大小k的最小堆，遍历一遍哈希表，与堆顶比较键值，大于堆顶则弹出堆顶元素并入堆。 ### 代码 ``` java class Solution { public int[] topKFrequent(int[] nums, int k) { Map map = new HashMap<>(); for (int num : nums){ if (map.containsKey(num)){ map.put(num, map.get(num) + 1); } else { map.put(num, 1); } } PriorityQueue pq = new PriorityQueue<>(k, new Comparator(){ @Override public int compare(Integer a, Integer b){ return map.get(a) - map.get(b); } }); for (int key : map.keySet()){ if (pq.size() < k){ pq.offer(key); } else if (map.get(pq.peek()) < map.get(key)){ pq.poll(); pq.offer(key); } } int[] res = new int[k]; for (int i = 0; !pq.isEmpty() && i < k; i++){ res[i] = pq.poll(); } return res; } } ``` ### 复杂度 - 时间复杂度：O(Nlogk)，遍历数组统计频次写入哈希表O(N)，维护的堆大小为k。 - 空间复杂的：O(N),最坏情况下每个元素都不一样。

[zhangyalei1026]

Main idea

Brute force. Hashtable + Sort.

Code

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        d = {}
        output = []
        for i in range(len(nums)):
            d[nums[i]] = d.get(nums[i], 0) + 1
        sort_order = sorted(d.items(), key = lambda x:x[1], reverse = True)
        for i in range(k):
            output.append(sort_order[i][0])
        return output

Complexity

Time complexity: O(nlogn) Space complexity: O(m)

[juleijs]

思路

哈希表+桶排序

代码

const topKFrequent  = (nums, k) => {
  let map = new Map(),
    arr = [...new Set(nums)];
  nums.map(num => {
    if (map.has(num)) {
      map.set(num, map.get(num) + 1);
    } else {
      map.set(num, 1);
    }
  })
  if (map.size <= k) {
    return [...map.keys()];
  }
  return bucketSort(map, k);
}

const bucketSort = (map, k) => {
  let arr = [],
    res = [];
 map.forEach((value, key) => {
   if (!arr[value]) {
     arr[value] = [key];
   } else {
     arr[value].push(key);
   }
 })
 for (let i = arr.length - 1; i >= 0 && res.length < k; i--) {
   if (arr[i]) {
     res.push(...arr[i])
   }
 }
 return res;
}

复杂度

• 时间复杂度：O(N)
• 空间复杂度：O(N)

[zhangzz2015]

前置知识

• 对于找k个最大，有两种标准方法，1种使用heap/priority_queue，第2种使用quick select方法。quick select方法和quick sort方法相同，只不过更早退出，因为只用找到k个最大，这k个不用排序。

公司

• 暂无

思路

• 方法1. 使用map用来统计frequent，再通过heap/priority_queue 用来找最大k个num。使用最小堆。维持堆的个数为k个，如果有新的frequent num大于堆顶，则把堆顶push，放入新的。时间复杂度为O(N) + O(NlogK) 空间复杂度为O(N)
• 方法2. 前面的过程相同， 使用quick select方法，调用parition partition把[left right] 选left 作为pivot，把所有元素和pivot比较，大于pivot放前面，小于pivot放后面，找到的index 为pivot的位置。当parition 返回的index，正好等于k-1，则表明找到最大k的元素，放的位置为[0, k-1]。否则要么在前半部分继续找，或者在后半部分接着找。该方法时间复杂度最差为O(N) + O(N) +O(N^2) ，空间复杂度为O(N)。

关键点

代码

• 语言支持：C++

C++ Code:

struct comp
{
    bool operator()(pair<int,int>& node1, pair<int,int>& node2)
    {
        if(node1.first == node2.first)  return node1.second < node2.second; 

        return node1.first > node2.first; 
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

     unordered_map<int, int>  recordFreq; 
        // o(n)
        for(int  i=0; i< nums.size(); i++)
        {
            recordFreq[nums[i]]++; 
        }
     priority_queue<pair<int,int>, vector<pair<int,int>>, comp> que ; // top is the smallest one. 

        for(unordered_map<int,int>::iterator it = recordFreq.begin(); it!=recordFreq.end(); it++)
        {
            if(que.size() < k)
            {
                que.push(make_pair((*it).second, (*it).first)); 
            }
            else if(que.top().first < (*it).second)
            {
                que.pop(); 
                que.push(make_pair((*it).second, (*it).first)); 
            }
        }
        vector<int> ret; 
        while(que.size())
        {
            ret.push_back(que.top().second);
            que.pop(); 
        }

        return ret; 
    }
};

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {

        unordered_map<int, int> record; 
        for(int i=0; i<nums.size(); i++)
            record[nums[i]]++; 
        // use quick select to find k. 

        vector<pair<int,int>> freqNum; 
        for(unordered_map<int,int>::iterator it = record.begin(); it!=record.end(); it++)
        {
            freqNum.push_back(make_pair((*it).second,(*it).first)); 
        }
        record.clear(); 

        int left =0; 
        int right=freqNum.size()-1; 
        for(int i =0; i<freqNum.size(); i++)
        {
            int index = partition(freqNum, left, right); 
            if(index==k-1)
                break; 
            else if(index < k-1 )
            {
                left = index+1; 
            }
            else
            {
                right = index-1;               
            }
        }
        vector<int> ret; 
        for(int i=0; i<k; i++)
            ret.push_back(freqNum[i].second); 
        return ret; 
    }

    /// 
    int partition(vector<pair<int,int>>& freqNum, int left, int right)
    {
        pair<int,int> pivot = freqNum[left];  
        while(left < right)
        {
            while(left < right && pivot.first>freqNum[right].first)
            {
                right --; 
            }
            swap(freqNum[left], freqNum[right]); 

            while(left < right && pivot.first<=freqNum[left].first)
            {
                left++; 
            }
            swap(freqNum[right], freqNum[left]); 
        }

        freqNum[left] = pivot; 
        return left; 

    }

};

[leungogogo]

LC347. Top K Frequent Elements

Method 1. Quick Select

Main Idea

Use quick select.

Code

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            int cnt = map.getOrDefault(nums[i], 0);
            map.put(nums[i], cnt + 1);
        }

        int[] A = new int[map.size()];
        int idx = 0;
        for (int key : map.keySet()) {
            A[idx++] = key;
        }

        quickSelect(A, 0, A.length - 1, k, map);
        int[] res = new int[k];
        for (int i = 0; i < k; ++i) {
            res[i] = A[i];
        }
        return res;
    }

    private void quickSelect(int[] A, int start, int end, int k, Map<Integer, Integer> map) {
        int len = end - start + 1;
        Random rand = new Random();
        swap(A, end, start + rand.nextInt(len));
        int pivot = map.get(A[end]);

        int f = start, s = start;
        while (f < end) {
            if (map.get(A[f]) > pivot) {
                swap(A, s++, f);
            }
            ++f;
        }
        swap(A, s, end);

        if (s == start + k - 1) {
            return;
        } else if (s < start + k - 1) {
            quickSelect(A, s + 1, end, k - (s - start + 1), map);
        } else {
            quickSelect(A, start, s - 1, k, map);
        }

    }

    private void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

Complexity Analysis

Time: average O(n), worst case O(n^2). Space: O(n)

[ruohai0925]

题目地址()

题目描述

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Python3

Python3 Code:

# 利用 heap
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        map = {}
        for num in nums:
            map[num] = map.get(num, 0) + 1

        temp = []
        res = []

        for key in map:
            temp.append((-map[key], key))
        heapq.heapify(temp)
        for i in range(k):
            res.append(heapq.heappop(temp)[1])

        return res

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(nlogn)$
• 空间复杂度：$O(n)$

[QiZhongdd]

-先排序，然后在利用双指针移动计算有多少个元素

• 得到元素的次数后先添加到数组中，如果大于K值则进行排序抛出顶部元素
• 用数组map返回对应的元素

var topKFrequent = function(nums, k) {
    let arr=[];
    let i=0;
    let j=0;
    nums.sort();
    while(nums[j]===nums[i]&&j<nums.length){
        j++;
        if(nums[i]!==nums[j]){
             arr.push([nums[i],j-i])
             arr.sort((a,b)=>b[1]-a[1]);
            if(arr.length>k){
                arr.pop()
            }
            i=j
        }
    }
    return arr.map(item=>item[0])
};

时间复杂度O(n2logn),空间复杂度On

[chang-you]

Thinking

Bucket Sort

Java Code

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        List<Integer>[] bucket = new ArrayList[nums.length + 1];
        for (int num : map.keySet()) {
            int freq = map.get(num);
            if (bucket[freq] == null) {
                bucket[freq] = new ArrayList<>();
            }
            bucket[freq].add(num);
        }

        List<Integer> resList = new ArrayList<>();
        for (int i = bucket.length - 1; i >= 0 && resList.size() < k; i--) {
            if (bucket[i] != null) {
                resList.addAll(bucket[i]);
            }
        }

        int[] res = new int[k];
        int j = 0;
        for (Integer val: resList.subList(0, k)){
            res[j++] = val;
        }
        return res;
    }
}

Complexity

Time = O(nlogn).
Space = O(n).

[okbug]

思路

哈希表统计次数，然后根据次数排序，并且返回前k个元素

代码

语言: JavaScript

var topKFrequent = function(nums, k) {
    let map = new Map();
    for (let s of nums) {
        map.set(s, (map.get(s) || 0) + 1);
    }
    return Array
            .from(map)
            .sort((a, b) => b[1] - a[1])
            .map((i) => i[0]).slice(0, k);
};

[shuichen17]

/*Time complexity: O(N)
  Space complexity: O(N)
*/
var topKFrequent = function(nums, k) {
    let map = new Map();
    let bucket = [];
    let res = [];
    for (let num of nums) {
        if (!map.has(num)) {
            map.set(num, 1);
        } else {
            map.set(num, map.get(num) + 1);
        }
    }
    for (const [key, value] of map) {
        if (bucket[value] === undefined) {
            bucket[value] = [];
        }
        bucket[value].push(key);
    }    
    let n = bucket.length - 1;
    for (let i = n; i >= 0; i--) {
        if (bucket[i] === undefined) continue;
        res.push(...bucket[i]);
        if (res.length === k) {
            break;
        }     
    }
    return res;  
};

[ginnydyy]

Problem

https://leetcode.com/problems/top-k-frequent-elements/

Notes

• Map + Bucket
  • Scan the input array, and use a map to store the <number, count> entries.
  • Iterate the map entries, and use a bucket (an array of list) to sotre the count and the matching numbers, the count is the index of the bucket(array), the matching numbers are store in the corresponding list.
  • Iterate the bucket from the end (highest frequency), and check the corresponding list, if the list is not null, then put the numbers from the list to the result array. And count for only k times.
• Map + Heap
  • Scan the input array, and use a map to store the <number, count> entries.
  • Use a min heap of map entries, and define a customized comparator to compare the entries' value (count). So the min element will be poll each time.
  • Iterate the map entries. When the heap size is less than k, keep offer the entries to the heap. When the heap size is greater than k, peek the value and compare to the entry's value, if the entry's value is smaller, then poll from the heap and offer then entry.
  • So the kth max numbers are always kept in the heap.
  • Put all the k numbers from the heap to the result array.

Solution

• Map + Bucket

  // map + bucket
  class Solution {
  public int[] topKFrequent(int[] nums, int k) {
      int[] result = new int[k];
      Map<Integer, Integer> map = new HashMap<>();
      List<Integer>[] bucket = new List[nums.length + 1];
      for(int n: nums){
          map.put(n, map.getOrDefault(n, 0) + 1);
      }
  
      for(Map.Entry<Integer, Integer> entry: map.entrySet()){
          int number = entry.getKey();
          int count = entry.getValue();
          if(bucket[count] == null){
              bucket[count] = new LinkedList<>();                
          }
          bucket[count].add(number);
      }
  
      int total = 0;
      for(int i = bucket.length - 1; i > 0 && total < k; i--){
          if(bucket[i] != null){
              for(int n: bucket[i]){
                  result[total] = n;
                  total++;
              }
          }
      }
  
      return result;
  }
  }

• Map + Heap

  // map + heap O(nlogk) when k<n, so O(nlogk) < O(nlogn); O(1) when k==n
  class Solution {
  public int[] topKFrequent(int[] nums, int k) {
      // k == n 
      // O(1)
      if(k == nums.length){
          return nums;
      }
  
      int[] result = new int[k];
      Map<Integer, Integer> map = new HashMap<>();
      PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((e1, e2) -> e1.getValue() - e2.getValue());
      // O(n)
      for(int n: nums){
          map.put(n, map.getOrDefault(n, 0) + 1);
      }
      // O(n*logk) => each heap push/pop is O(logk), there are n elements to operate, so total O(n*logk)
      for(Map.Entry<Integer, Integer> entry: map.entrySet()){
          if(minHeap.size() < k){
              minHeap.offer(entry);
          }else if(minHeap.peek().getValue() < entry.getValue()){
              minHeap.poll();
              minHeap.offer(entry);
          }
      }
      for(int i = 0; i < k; i++){
          result[i] = minHeap.poll().getKey();
      }
  
      return result;
  }
  }

Complexity

• Map + Bucket
  • Time: O(n) n is the size of the array.
  • Space: O(n) for the map and bucket.
• Map + Heap
  • Time: O(nlogk) when k < n; O(1) when k == n.
  • Space: O(n + k) => O(n) when k < n. So the space if mainly for the map. O(1) when k == n.

[RonghuanYou]

from heapq import *
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        numFrequency = {}
        for num in nums:
            numFrequency[num] = numFrequency.get(num, 0) + 1

        minHeap = []
        for num, frequency in numFrequency.items():
            heappush(minHeap, (frequency, num))
            if len(minHeap) > k:
                heappop(minHeap)

        topkFrequency = []
        while(minHeap):
            topkFrequency.append(heappop(minHeap)[1])

        return topkFrequency

[MoncozGC]

from heapq import *
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        numFrequency = {}
        for num in nums:
            numFrequency[num] = numFrequency.get(num, 0) + 1

        minHeap = []
        for num, frequency in numFrequency.items():
            heappush(minHeap, (frequency, num))
            if len(minHeap) > k:
                heappop(minHeap)

        topkFrequency = []
        while(minHeap):
            topkFrequency.append(heappop(minHeap)[1])

        return topkFrequency

[lilyzhaoyilu]

class Solution {
public:

    static bool cmp(pair <int, int>& m, pair<int, int>& n){
        return m.second > n.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (auto& v : nums) {
            freq[v]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for (auto& [num, count] : freq) {
            if (q.size() == k) {
                if (q.top().second < count) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }
        vector<int> ret;
        while (!q.empty()) {
            ret.emplace_back(q.top().first);
            q.pop();
        }
        return ret;
    }

};

c++也太难了吧... 头秃

[StefanLeeee]

思路

hashmap存储值和出现的次数 然后将出现次数多的前k个，放入新的队列中

代码

public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> objects = new HashMap<>();
        for (int num : nums) {
            objects.put(num, objects.getOrDefault(num, 0) + 1);
        }
        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        //出现频率前 k 高的元素
        for (Map.Entry<Integer, Integer> entry : objects.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }

复杂度

• 时间复杂度：O(NlogK)
• 空间复杂度：O(N)