【Day 20 】2022-11-20 - 347. 前 K 个高频元素

[azl397985856]

347. 前 K 个高频元素

入选理由

暂无

题目地址

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

前置知识

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

  题目描述

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

 

示例 1:

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

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

提示：

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

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

[whoam-challenge]

思路

快排

代码

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]: count = collections.Counter(nums) num_cnt = list(count.items()) topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1) return [item[0] for item in topKs]

def findTopK(self, num_cnt, k, low, high):
    pivot = random.randint(low, high)
    num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]
    base = num_cnt[low][1]
    i = low
    for j in range(low + 1, high + 1):
        if num_cnt[j][1] > base:
            num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]
            i += 1
    num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
    if i == k - 1:
        return num_cnt[:k]
    elif i > k - 1:
        return self.findTopK(num_cnt, k, low, i - 1)
    else:
        return self.findTopK(num_cnt, k, i + 1, high)

复杂度分析

-时间复杂度 平均O(n) -空间复杂度 O(n)

[mayloveless]

思路

记录每个元素出现的频率，用小顶堆选出topk，大于堆顶可入选

代码

var topKFrequent = function(nums, k) {
    // value -> count
    const counts = {};
    for(let i=0;i<nums.length;i++) {
        if (counts[nums[i]] !== undefined) {
            counts[nums[i]] += 1;
        } else {
            counts[nums[i]] = 1;
        }
    }

    let queue = new MinPriorityQueue({priority: node => node.count})
    for (let num in counts) {
        const count = counts[num];
        if (queue.size() < k) {
            queue.enqueue(QElement(num, count))
        } else {
            if (queue.front().element.count < count) {
                queue.dequeue();
                queue.enqueue(QElement(num, count))
            }
        } 
    }

    let result = [];
    for (let i=0; i < k; ++i) {
        result.push(queue.dequeue().element.val)
    }
    return result
};

function QElement (num, count) {
    return {
        val: num === undefined ? 0 : num, 
        count: count === undefined ? 0 : count, 
    }
}

复杂度

时间：0(nlogn) n为哈希遍历，logn为堆排序 空间：O(n+k) 哈希+堆

[heng518]

class Solution { public: vector topKFrequent(vector& nums, int k) { priority_queue<pair<int, int>> q; map<int, int> m; vector res;

    for(size_t i = 0; i < nums.size(); i++)
        m[nums[i]]++;

    for(map<int,int>::iterator it = m.begin(); it != m.end(); it++)
        q.push({it->second, it->first});

    for(int i = 0; i < k; i++)
    {
        res.push_back(q.top().second);
        q.pop();
    }

    return res;
}

};

[chenming-cao]

解题思路

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

方法二：哈希表+堆排序。哈希表储存数字和对应出现次数。建立一个容量为k的最小堆。遍历哈希表，将表中元素存入最小堆中。当堆的容量超过k时，去除堆顶出现次数最少的元素。最后返回堆中对应的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> counts = new HashMap<>();
        for (int n: nums) {
            counts.put(n, counts.getOrDefault(n, 0) + 1);
        }
        int[] res = new int[k];
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (a, b) -> counts.get(a) - counts.get(b)
        );
        for (int key: counts.keySet()) {
            minHeap.offer(key);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = minHeap.poll();
        }
        return res;
    }
}

复杂度分析

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

[zhiyuanpeng]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        nums = collections.Counter(nums)
        min_key, min_val = 0, float("inf")
        ans = {}
        for key, val in nums.items():
            if len(ans) < k:
                ans[key] = val
                if val < min_val:
                    min_key = key
                    min_val = val
            else:
                if val > min_val:
                    del ans[min_key]
                    ans[key] = val
                    min_val = float("inf")
                    for kk, vv in ans.items():
                        if vv < min_val:
                            min_val = vv
                            min_key = kk
        return ans.keys()

time O(N) spce O(N)

[Ryanbaiyansong]

class Solution:
    def topKFrequent(self,a: List[int], k: int) -> List[int]:
        n = len(a)
        # # 经典top k 问题
        # minHeap = []

        # val2freq = Counter(a)

        # for val, freq in val2freq.items():
        #     heapq.heappush(minHeap, (freq, val))

        #     while len(minHeap) > k:
        #         heapq.heappop(minHeap)

        # # print(minHeap)

        # return [v for _, v in minHeap]

        # 解法二: 快速选择算法
        # val2freq = Counter(a)
        # # inplace 交换vals里面的元素
        # vals = list(val2freq.keys())
        # t = len(vals) - k
        # def quick_select(l, r):
        #     if l >= r:
        #         return 
        #     pivot_index = partition(l, r)

        #     if pivot_index == t:
        #         return 
        #     elif pivot_index < t:
        #         quick_select(pivot_index + 1, r)
        #     else:
        #         quick_select(l, pivot_index - 1)
        # def partition(l, r):
        #     i = l - 1
        #     pivot = val2freq[vals[r]]
        #     for j in range(l ,r):
        #         if val2freq[vals[j]] < pivot:
        #             i += 1
        #             swap(i, j)
        #     swap(i+1, r)
        #     return i + 1

        # def swap(l, r):
        #     temp = vals[l]
        #     vals[l] = vals[r]
        #     vals[r] = temp

        # quick_select(0, len(vals) - 1)
        # return vals[t:]

        # 解法三: 计数排序
        val2freq = Counter(a)
        count2vals = [[] for _ in range(n + 1)] # 最多出现n次
        # print(count2vals)
        for val, freq in val2freq.items():
            count2vals[freq].append(val)

        # print(count2vals)

        res = []
        for i in range(len(count2vals) - 1, -1, -1):
            for val in count2vals[i]:
                res.append(val)
                if len(res) == k:
                    return res

[Frederickfan]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int n: nums) {
            counts.put(n, counts.getOrDefault(n, 0) + 1);
        }
        int[] res = new int[k];
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(
            (a, b) -> counts.get(a) - counts.get(b)
        );
        for (int key: counts.keySet()) {
            minHeap.offer(key);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            res[i] = minHeap.poll();
        }
        return res;
    }
}

[zjsuper]

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

    dic = sorted(dic, key = dic.get, reverse = True)
    #print(dic)
    ans = []
    count = 0
    for i in dic:
        if count == k:
            break
        ans.append(i)
        count += 1
    return ans

[JancerWu]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
        for (int key : map.keySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(new int[]{key, map.get(key)});
            } else {
                if (map.get(key) > minHeap.peek()[1]) {
                    minHeap.poll();
                    minHeap.offer(new int[]{key, map.get(key)});
                }
            }
        }
        int[] ans = new int[k];
        int cnt = 0;
        while (!minHeap.isEmpty()) {
            ans[cnt++] = minHeap.poll()[0];
        }
        return ans;

    }
}

[snmyj]

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
              HashMap<Integer, Integer> count = new HashMap();
                for (int n : nums) count.put(n, count.getOrDefault(n, 0) + 1);
         PriorityQueue<Integer> heap = new PriorityQueue<Integer>((a, b) -> count.get(a) - count.get(b));
        for (int n : count.keySet()) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }
        List<Integer> top_k = new LinkedList();
        while (!heap.isEmpty())
            top_k.add(heap.poll());
        return top_k;
    }
}

[Albert556]

class Solution { private: map<int, int> frep;

// 最小堆 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

public: vector topKFrequent(vector &nums, int k) { for (auto it : nums) { frep[it]++; } // 堆中元素为 [频次，数值] 元组，并根据频次维护小顶堆特性 for (auto it : frep) { if (q.size() != k) { q.push(make_pair(it.second, it.first)); } else { if (it.second > q.top().first) { q.pop(); q.push(make_pair(it.second, it.first)); } } } vector res; while (q.size()) { res.push_back(q.top().second); q.pop(); } return vector(res.rbegin(), res.rend()); } };

[Alyenor]

function topKFrequent(nums: number[], k: number): number[] {
    const m = new Map<number,number>()
    for(const num of nums){
        m.set(num, 1+(m.has(num)?m.get(num)+1:0))   
    }
    const arr = Array.from(m)
    const arrSorted = arr.sort((a,b)=>b[1]-a[1])
    const kArr =arrSorted.slice(0,k)
    return kArr.map(item=>item[0])
};

[zywang0]

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);
        }
        //build max heap
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
        for(Map.Entry<Integer, Integer> entry : map.entrySet()) {
            queue.offer(entry);
        }
        int[] ans = new int[k];
        int index = 0;
        while(!queue.isEmpty() && index < k){
            ans[index++] = queue.poll().getKey();
        }
        return ans;
    }
}

[klspta]

思路

小根堆维护k个最大值； map记录值对应的次数；

    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int n :  nums){
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> {
            return map.get(a) - map.get(b);
        });
        for(Integer key : map.keySet()){
            if(queue.size() < k){
                queue.add(key);
            }else if(map.get(key) > map.get(queue.peek())){
                queue.add(key);
                queue.remove();
            }
        }
        int[] res = new int[k];
        int i = 0;
        while(!queue.isEmpty()){
            res[i++] = queue.poll();
        }
        return res;
    }

[Abby-xu]

思路

。。。

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import heapq
        from collections import Counter, defaultdict
        heap = [(-1*v1, k1) for k1,v1 in Counter(nums).items()] # O(N) to build the heap
        heapq.heapify(heap) # O((n-k) log n). Worst case O(n log n).
        result = []
        for i in range(k):
            result.append(heapq.heappop(heap)[1]) # O(logN) / O((n-k) log n) for the pops
        return result

复杂度

见代码

[gsw9818]

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [i[0] for i in Counter(nums).most_common(k)]

[StaringWhere]

思路

一般第k个问题会用堆或者快速选择算法，但这道题需要排序的东西是有限种可能的，所以可以用map来变成线性复杂度。

代码

class Solution {
  public:
  vector<int> topKFrequent(vector<int>& nums, int k) {
      unordered_map<int, int> num_freq;
      unordered_map<int, vector<int>> freq_num;
      vector<int> res;
      for (auto it : nums) {
          if (num_freq.count(it)) {
              num_freq[it]++;
          }
          else {
              num_freq[it] = 1;
          }
      }
      int freq_max = 0;
      for (auto it: num_freq) {
          if (it.second > freq_max) {
              freq_max = it.second;
          }
          if (freq_num.count(it.second)) {
              freq_num[it.second].push_back(it.first);
          }
          else {
              freq_num[it.second] = vector<int> {it.first};
          }
      }
      int count = 0;
      for (int i = freq_max; count < k; i--) {
          if (freq_num.count(i)) {
              for (int j = 0; j < freq_num[i].size() && count < k; j++, count++) {
                  res.push_back(freq_num[i][j]);
              }
          }
      }
      return res;
  }
};

复杂度分析

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

[testplm]

class Solution(object):
    def topKFrequent(self, nums, k):
        hs = {}
        frq = {}
        for i in range(0,len(nums)):
            if nums[i] not in hs:
                hs[nums[i]] = 1
            else:
                hs[nums[i]] += 1

        for z,v in hs.iteritems():
            if v not in frq:
                frq[v] = [z]
            else:
                frq[v].append(z)
        arr = []

        for x in range(len(nums),0,-1):
            if x in frq:
                for i in frq[x]:
                    arr.append(i)
        return [arr[x] for x in range(0, k)]

• Time:O(n)
• Space:O(n)

[tiandao043]

思路

map+优先队列

代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans;
        map<int,int> m;
        for(int i=0;i<nums.size();i++){
            if(m.count(nums[i])){
                m[nums[i]]++;
            }else{m[nums[i]]=1;}
        }
        map<int, int>::iterator iter;
        iter = m.begin();
        priority_queue<pair<int, int>> a;
        pair<int, int> b;
        while(iter != m.end()) {
            b.first=iter->second;
            b.second=iter->first;
            a.push(b);
            iter++;
        }
        while (!a.empty()&&k) 
        {
            ans.push_back(a.top().second);
            // cout << a.top().first << ' ' << a.top().second << '\n';
            a.pop();k--;
        }
        return ans;
    }
};

复杂度

O(N logK) O(N)

快排选前k也行

[yuexi001]

思路

哈希表+小顶堆

代码

C++ Code:

class Solution {
public:
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map; 
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { 
                pri_que.pop();
            }
        }

        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

复杂度分析

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

[buer1121]

class Solution: def topKFrequent(self, nums: List[int], k: int) -> List[int]:

    # count = collections.Counter(nums)
    # return [item[0] for item in count.most_common(k)]

    import random
    count = collections.Counter(nums)
    new_num=list(count.items())
    l=0
    r=len(new_num)-1
    def partion(new_num,k,l,r):
        idc=random.randint(l,r)
        new_num[idc],new_num[r]=new_num[r],new_num[idc]
        less=l-1
        pivot=new_num[r][1]
        i=l
        while i<=r:
            if new_num[i][1]>=pivot:
                new_num[i],new_num[less+1]=new_num[less+1],new_num[i]
                less+=1
            i+=1

        if less==k-1:
            return new_num[:k]

        elif less>k-1:
            return partion(new_num,k,l,less-1)
        else:
            return partion(new_num,k,less+1,r)

    topk=partion(new_num,k,l,r)
    return [item[0] for item in topk]

[A-pricity]

var topKFrequent = function(nums, k) {
    //前k个高频元素
    let hash = new Map();
        //频率统计
    for(let i of nums){
        if(!hash.has(i)) hash.set(i,1);
        else hash.set(i,hash.get(i)+1);
    }
    nums=new Array(hash.size);
    let j=0;
    for(let [key,value] of hash){
        nums[j++]=[key,value];
    }
    getK(nums,0,nums.length-1,k);
    let res=new Array(k);
    for(let i=0;i<k;++i){
        res[i] = nums[i][0];
    }
    return res;
};

//分治   
var getK = function(nums,left,right,k){
    if(left>=right) return ;
    let temp = quikSort(nums,left,right,k);
    if(temp+1==k+left) return ;
    else if(temp+1<k+left){
        getK(nums,temp+1,right,k-(temp+1-left));  //前面的temp+1-left已经符合要求 找剩下的k-(temp+1-left)个最大元素
    } else getK(nums,left,temp-1,k);      //继续找前k个最大元素
    return ;
}

var quikSort = function(nums,left,right){
    if(left>=right) return left;
    let pivot = nums[left];
    let i=left,j=right;
    while(i<j){
        while(nums[j][1]<pivot[1] && i<j) --j;
        nums[i] = nums[j];
        while(nums[i][1]>=pivot[1] && i<j) ++i;
        nums[j] = nums[i];
        if(i==j) nums[i] = pivot;
    }
    return i;
}

[darwintk]

思路

哈希表+快排

代码

class Solution(object):
    def topKFrequent(self, nums, k):
        count = collections.Counter(nums)
        num_cnt = list(count.items())
        topKs = self.findTopK(num_cnt, k, 0, len(num_cnt) - 1)
        return [item[0] for item in topKs]

    def findTopK(self, num_cnt, k, low, high):
        pivot = random.randint(low, high)
        num_cnt[low], num_cnt[pivot] = num_cnt[pivot], num_cnt[low]
        base = num_cnt[low][1]
        i = low
        for j in range(low + 1, high + 1):
            if num_cnt[j][1] > base:
                num_cnt[i + 1], num_cnt[j] = num_cnt[j], num_cnt[i + 1]
                i += 1
        num_cnt[low], num_cnt[i] = num_cnt[i], num_cnt[low]
        if i == k - 1:
            return num_cnt[:k]
        elif i > k - 1:
            return self.findTopK(num_cnt, k, low, i - 1)
        else:
            return self.findTopK(num_cnt, k, i + 1, high)

[xuanaxuan]

快速选择

思路

基本流程如下：

1. 首先选定一个轴心值 p。
2. 将数组中小于 p 的值移到数组左端，其他移动到数组右端。
3. 计算轴心左端的数 (包括轴心自己) 有多少，记为 count
4. 如果 count 正好为 k，则返回此时轴心值，此值即为第 k 小的数。
5. 如果左端的数 count 大于 k，说明在左端，所以只递归左边即可。
6. 如果不在左端，只递归在右边寻找。

代码

//
var topKFrequent = function (nums, k) {
  const counts = {};
  for (let num of nums) {
    counts[num] = (counts[num] || 0) + 1;
  }
  // 【次数，值】
  let pairs = Object.keys(counts).map((key) => [counts[key], key]);

  select(0, pairs.length - 1, k);
  return pairs.slice(0, k).map((item) => item[1]);

  // 快速选择
  function select(left, right, offset) {
    if (left >= right) {
      return;
    }
    const pivotIndex = partition(left, right);
    if (pivotIndex === offset) {
      return;
    }

    if (pivotIndex <= offset) {
      select(pivotIndex + 1, right, offset);
    } else {
      select(left, pivotIndex - 1,offset);
    }
  }

  // 拆分数组为两个part
  function partition(left, right) {
    const [pivot] = pairs[right];
    let cur = left;
    let leftPartIndex = left;
    while (cur < right) {
      if (pairs[cur][0] > pivot) {
        swap(leftPartIndex++, cur);
      }
      cur++;
    }
    swap(right, leftPartIndex);
    return leftPartIndex;
  }

  function swap(x, y) {
    const term = pairs[x];
    pairs[x] = pairs[y];
    pairs[y] = term;
  }
};

复杂度

• 时间复杂度: O(N), 最坏能到 O(N^2)
• 空间复杂度: O(N)

[SJ941127]

思路

哈希表存储每个值的个数，然后对每个值的个数进行排序，取k个，并返回

代码

var topKFrequent = function(nums, k) {
  var map = new Map()
  var len = nums.length
  for (var i = 0; i < len; i++) {
    map.set(nums[i], (map.get(nums[i]) || 0) + 1)
  }
  return [...map]
    .sort((a, b) => b[1] - a[1])
    .filter((v, i) => i < k)
    .map(v => v[0])
};

[want2333]

347. 前 K 个高频元素

构造一个大小为K的堆来降低算法复杂度

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> res;
        while (!q.empty()) {
            res.emplace_back(q.top().first);
            q.pop();
        }
        return res;
    }
};

[HWFrankFung]

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

[bookyue]

code

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

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));

        for (var e : count.entrySet()) {
            int[] p = {e.getKey(), e.getValue()};
            if (k > minHeap.size())
                minHeap.add(p);
            else if (p[1] > minHeap.element()[1]) {
                minHeap.remove();
                minHeap.add(p);
            }
        }

        return minHeap.stream().mapToInt(e -> e[0]).toArray();
    }

[wtdcai]

代码

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

        pri_que = []
        for key, val in alldict.items():
            heapq.heappush(pri_que, (val,key))
            if len(pri_que) > k:
                heapq.heappop(pri_que)

        out = [0]*k
        for j in range(k-1, -1, -1):
            out[j] = heapq.heappop(pri_que)[1]

        return out

复杂度分析

O(nlogk)
O(n)

[liuajingliu]

代码实现

javaScript

let topKFrequent = function(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)
    })

    // 如果元素数量小于等于 k
    if(map.size <= k) {
        return [...map.keys()]
    }

    return bucketSort(map, k)
};

// 桶排序
let bucketSort = (map, k) => {
    let arr = [], res = []
    map.forEach((value, key) => {
        // 利用出现频率作为下标，将数据分配到各个桶中
        if(!arr[value]) {
            arr[value] = [key]
        } else {
            arr[value].push(key)
        }
    })
    // 倒序遍历获取出现频率最大的前k个数
    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)$

[Dou-Yu-xuan]

class Solution:
def topKFrequent(self, nums, k: int) -> int:

    heap = [(-1 * v1, k1) for k1, v1 in Counter(nums).items()]  # O(N) to build the heap
    heapq.heapify(heap)  # O((n-k) log n). Worst case O(n log n).
    result = []
    for i in range(k):
        result.append(heapq.heappop(heap)[1])  # O(logN) / O((n-k) log n) for the pops
    return result

[Alexno1no2]

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # 先统计各数字数目，然后找出数目的第k大数
        cnt = Counter(nums)
        l = list(cnt.values())

        # 小根堆
        def findKthLargest(nums, k):
            maxHeap = []
            for x in nums:
                heapq.heappush(maxHeap, -x)
            for _ in range(k - 1):
                heapq.heappop(maxHeap)
            return -maxHeap[0]

        ans = list()
        n = findKthLargest(l, k)
        for k, v in cnt.items():
            if v >= n:
                ans.append(k)
        return ans

[saitoChen]

思路

用的不是二叉堆，使用的是哈希+排序

代码

var topKFrequent = function(nums, k) {
    const map = new Map()
    for(let i = 0; i < nums.length; i++) {
        if (!map.get(nums[i])) {
            map.set(nums[i], 1)
        } else {
           map.set(nums[i], map.get(nums[i]) + 1)
        }
    }
    let arr = Array.from(map).sort((a,b) => b[1] - a[1])
    let result = arr.slice(0, k).map(num => num[0])
    return result
};

复杂度分析

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

[AstrKing]

思路

首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前 k 个高频元素，就相当于找出「出现次数数组」的前 k 大的值。

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.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];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.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(n)

空间复杂度：O(n)

[LiHua1997]

    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];    // 结果数组
        Map<Integer, Integer> map = new HashMap();
        // 统计数组中各元素出现的次数
        for(int num : nums){
            if(map.containsKey(num)){
                map.put(num, map.get(num) + 1);
            }else{
                map.put(num, 1);
            }
        }

        int maxTimes = 0;    // 出现最多的元素的出现次数
        // 找出出现次数最多的元素出现的次数
        for(Map.Entry<Integer, Integer> entry : map.entrySet()){
            if(entry.getValue() > maxTimes){
                maxTimes = entry.getValue();
            }
        }

        // 按出现次数从大到小添加到结果数组
        while(k > 0){
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
                if(entry.getValue() == maxTimes){
                    res[k - 1] = entry.getKey();
                    k--;
                }
            }
            maxTimes--;
        }

        return res;
    }

[MaylingLin]

思路

使用哈希表+堆排序

代码

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = list(collections.Counter(nums).items())
        count = list(map(lambda x: (-x[1], x[0]), count))
        heapq.heapify(count)
        res = []
        for _ in range(k):
            res.append(heapq.heappop(count)[1])
        return res

复杂度

• Time: $O(klogM)$
• Space: $O(M),M是不同元素个数$

[FlipN9]

/**
    思路一: 堆      TC:O(nlogk) SC:O(n) for hashmap, O(k) for PQ
*/
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : freq.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[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        resurn ret;
    }
}

[andyyxw]

function topKFrequent(nums: number[], k: number): number[] {
  const statistic: { [k: number]: number } = nums.reduce((acc, cur) => (acc[cur] = (acc[cur] || 0) + 1, acc), {})
  const queue = new MinPriorityQueue({ priority: (item: [number, number]) => item[1] })
  for (const item of Object.entries(statistic)) {
    queue.enqueue(item)
    if (queue.size() > k) queue.dequeue()
  }
  const res: number[] = []
  while (queue.size()) res.push(queue.dequeue().element[0])
  return res
}

[zhuzhu096]

class Solution { public: vector topKFrequent(vector& nums, int k) { unordered_map<int,int> mp; //先计算每个元素的频数 int length=nums.size(); for(int i=0;i<length;i++){ mp[nums[i]]++; } priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > heap; //利用 优先队列 进行排序 for(auto j:mp){ heap.push(make_pair(j.second,j.first)); if(heap.size()>k){ heap.pop(); } } vector arr; //将符合题意的元素放入数组arr中，并返回结果 for(int i=0;i<k;i++){ arr.push_back(heap.top().second); heap.pop(); } return arr;

}

};

[paopaohua]

思路

哈希表 + 堆排序

代码

class Solution {
public int[] topKFrequent(int[] nums, int k) {
// 哈希表  + 将每个数及其对应的个数放进去
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int  num : nums){
map.put(num,map.getOrDefault(num,0) + 1);// 有相同的数就+ 1
}
// 堆
PriorityQueue<int[]> queue =  new PriorityQueue<int[]>(new Comparator<int[]>(){
public int compare(int[] m, int[] n) {
return m[1] - n[1];  // 定义比较器规则：出现次数多的在前面
}
});
for(Map.Entry<Integer, Integer> entry : map.entrySet()){ // 将map中的值对应起来放在set中
int num = entry.getKey(), count = entry.getValue();
if(queue.size() == k){ //有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];
//将堆中的数组的num放在ret中
for(int i = 0;i < k; i++){
ret[i] = queue.poll()[0];
}
return ret;
}
}

复杂度

• 时间：o(nlogn) n为数组长度
• 空间：o(n) n为数组长度

[RestlessBreeze]

思路

堆

代码

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]++;
        }

        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;
    }
};

## 复杂度
时间:o(nlogk)
空间:o(n)

[Jetery]

347. 前 K 个高频元素

思路

1. 用hashmap记录每个数出现的次数

2. 创建大小为k的小根堆, 遍历hashmap, 如果mp[key] 大于堆顶元素, 则弹出

   需要的知识:

   小根堆 + 哈希表

   代码 (cpp)

   class Solution {
   public:
   typedef pair<int, int> PII;
   vector<int> topKFrequent(vector<int>& nums, int k) {
       unordered_map<int, int> mp;
       for (int elem : nums) mp[elem]++;
   
       priority_queue<PII, vector<PII>, greater<PII>> q;
       for (auto &[a, b] : mp) {
           if (q.size() < k) {
               q.push(make_pair(b, a));
           } else {
               if (b > q.top().first) {
                   q.pop();
                   q.push(make_pair(b, a));
               }
           }
       }
   
       vector<int> ans;
       while (q.size()) {
           ans.push_back(q.top().second);
           q.pop();
       }
   
       return ans;
   }
   };

   复杂度分析

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

[tzuikuo]

思路

用map

代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int,int> mymap;
        int n=nums.size(),maxtemp=0,maxnum;
        vector<int> results;
        for(int i=0;i<n;i++){
            if(mymap.find(nums[i])!=mymap.end()) mymap[nums[i]]++;
            else mymap[nums[i]]=1;
        }
        while(k){
            maxtemp=0;
            for(auto it=mymap.begin();it!=mymap.end();it++){
                if(it->second>maxtemp){
                    maxtemp=it->second;
                    maxnum=it->first;
                }
            }
            results.push_back(maxnum);
            mymap[maxnum]=0;
            k--;
        }
        return results;
    }
};

复杂度分析

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

[sclihuiming]

type tt struct {
    num    int
    amount int
}

func topKFrequent(nums []int, k int) []int {
    record := make(map[int]int)
    arr := []*tt{}
    seq := 0
    for _, num := range nums {
        if index, ok := record[num]; ok {
            arr[index].amount += 1
        } else {
            record[num] = seq
            seq++
            arr = append(arr, &tt{
                num:    num,
                amount: 1,
            })
        }
    }
    sort.Slice(arr, func(i, j int) bool {
        a, b := arr[i], arr[j]
        return a.amount > b.amount
    })
    res := make([]int, k)
    for index := 0; index < k; index++ {
        res[index] = arr[index].num
    }
    return res
}

[neado]

思路

map存数字及次数， 构建一个大小为k的小顶堆， 遍历map，与堆顶元素比较，大的赋值为堆顶

代码

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        //计数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        // 数组第1个元素值，第2个元素次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] a, int[] b) {
                //比较次数，构建小顶堆
                return a[1] - b[1];
            }
        });
        //遍历map，拿出来与堆封顶部比较
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int num = entry.getKey()；
            int c = entry.getValue();
            //堆维护为k大小
            if (queue.size() == k) {
                //比较堆顶数据，哪个大哪个加入堆顶
                if (queue.peek()[1] < c) {
                    queue.poll();
                    queue.offer(new int[]{num, c});
                }
            } else {
                queue.offer(new int[]{num, c});
            }
        }
        //最后取出值
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

算法复杂度

TIME:O(nlogk) SPACE:O(n)

[xiaaller]

function topKFrequent(nums: number[], k: number): number[] { const map = new Map<number, number>()

for (let i = 0; i < nums.length; i++) {
    if (!map.has(nums[i])) {
        map.set(nums[i], 1)
    } else {
        let count = map.get(nums[i]) as number
        map.set(nums[i], count + 1)
    }
}

const arr = Array.from(map)
arr.sort((a, b) => b[1] - a[1])

const result = arr.map((v) => v[0])
// console.log(result.slice(0, k))

return result.slice(0, k)

}

[asuka1h]

思路

用hashmap存起来 再放进最大堆里

code

struct cmp {
    bool operator()(pair<int,int> const& p1, pair<int,int> const& p2)
    {

        return p1.second < p2.second;
    }
};

class Solution {
public:

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hashMap;
        for(auto i: nums){
            ++hashMap[i];
        }
        priority_queue<pair<int,int>, vector<pair<int,int>>, cmp> heap;
        for(auto i: hashMap){
            heap.push(make_pair(i.first,i.second));
        }
        vector<int>ret;
        for(int i = 0; i < k; ++i){

            ret.push_back(heap.top().first);
            heap.pop();
        }
        return ret;
    }
};

复杂度

时间: 插入hashmap 为O(n), n是整个vector长度, 插入heap是logN, n是vector里unique的数字的长度, 删除是logN 空间: O(N) n是vector里unique的数字的个数

[chiehw]

基本思路：

• 利用堆获取前 k 个。

大致步骤：

1. 遍历数组，统计出现次数。
2. 将数组存入小顶堆，然后维护小顶堆的大小为 k。
3. 最后将小顶堆转换为数组返回。

代码：

class Solution {
public:
    static bool cmp(const pair<int, int>& n, const pair<int, int>& m){
        return n.second > m.second;
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> occurrences;
        for(const auto& num: nums){
            occurrences[num]++;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for(const auto &[num, count]: occurrences){
            if(q.size() < k){
                q.emplace(num, count);
            }else{
                if(q.top().second < count){
                    q.pop();
                    q.emplace(num, count);
                }
            }
        }

        vector<int> ans;
        while(!q.empty()){
            ans.emplace_back(q.top().first);
            q.pop();
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：O(Nlogk)，哈希表记录的时间复杂度是 O(N)，每次堆操作需要 O(logk)，累计需要 O(Nlogk)。
• 空间复杂度：O(N)

[BruceZhang-utf-8]

class Solution { public int[] topKFrequent(int[] nums, int k) { HashMap<Integer, Integer> map = new HashMap<>(); for (int num : nums) { if(map.containsKey(num)){ Integer value = map.get(num); map.put(num,value+1); }else{ map.put(num,1); } } // 遍历map，用最小堆保存频率最大的k个元素 PriorityQueue pq = new PriorityQueue<>(new Comparator() { @Override public int compare(Integer a, Integer b) { return map.get(a) - map.get(b); } }); for (Integer key : map.keySet()) { if (pq.size() < k) { pq.add(key); } else if (map.get(key) > map.get(pq.peek())) { pq.remove(); pq.add(key); }} // 取出最小堆中的元素

   int[] res = new int[k];

    for (int i = 0; i < k; i++) {
        res[i]=(pq.remove());
    }

    return res;

}

}

[miduoliu]

Thought: When it comes to "Top K frequent", I would consider minHeap or maxHeap to do this kind of question. Use a hashmap to store the frequency of integer, and put the frequency into the minHeap. If the heap size larger than k. pop out the first element in queue. After traverse the whole map, everything left in pq is the final answer.

Code:

public int[] topKFrequent(int[] nums, int k) {
        if (k == nums.length) return nums;
        HashMap<Integer, Integer> hm = new HashMap<>();
        for (int i : nums)
            hm.put(i, hm.getOrDefault(i, 0) + 1);

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)-> hm.get(a) - hm.get(b));

        for (int i : hm.keySet()) {
            pq.add(i);
            if (pq.size() > k) 
                pq.poll();
        }

        int[] ret = new int[k];
        while (k > 0)
            ret[--k] = pq.poll();

        return ret;
    }

Time Complexity: O(nlogk) Space Complexity: O(n + k)