【Day 20 】2024-04-27 - 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 是数组大小。

[Dtjk]

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

[xil324]

/**

• @param {number[]} nums
• @param {number} k

• @return {number[]} */ var topKFrequent = function(nums, k) { const frequencyMap = {}; for(const num of nums) { if(!(num in frequencyMap)) { frequencyMap[num] = 1; } else { frequencyMap[num] += 1; } }

  const sortedFrequencyMap = Object.entries(frequencyMap).sort((a,b) => b[1] - a[1]); const res = []; for(let i = 0; i < k; i++) { res.push(sortedFrequencyMap[i][0]) } return res; };

[CathyShang]

思路：

• 哈希表统计频次
• 堆排序

代码

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> hash;
        int n = nums.size();
        for(int i = 0; i < n; i++){
            auto it = hash.find(nums[i]);
            if(it != hash.end()){
                hash[nums[i]] += 1;
            }else{
                hash[nums[i]] = 1;
            }
        }
        // 排序 堆（不会）
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
        for(auto& [num, count]: hash){
            std::cout << num <<", "<<count <<endl;
            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;
    }
};

• 时间 O(NlogN)
• 空间 O(N)

[zhiyuanpeng]

from collections import Counter, defaultdict
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        return heapq.nlargest(k, freq.keys(), key=lambda x: freq[x]

Time O(Nlogk) space O(N)

[YANGLimbo]

懒惰的map写法，键值对储存完再根据value排序。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        std::map<int,int> freqMap;
        for(auto& num : nums){
            if(freqMap.find(num)!=freqMap.end()){
                freqMap[num] = freqMap[num]+1; // 这里能不能用++
            }else{
                freqMap[num] = 1;
            }
        }
        vector<pair<int,int>> compVec(freqMap.begin(),freqMap.end());
        sort(compVec.begin(),compVec.end(),[](const pair<int,int>& a, const pair<int,int>& b){
            return a.second > b.second;
        });

        vector<int> ans(k);
        std::transform(compVec.begin(),compVec.begin()+k, ans.begin(), 
        [](const pair<int,int> p){
            return p.first; // 返回key
            /*
            std::transform 是 C++ 标准库中的一个非常有用的算法，它属于 <algorithm> 头文件。
            这个函数通常用于将一个函数或操作应用于一个输入范围的元素，并将结果存储到另一个输出
            范围。它非常适合进行元素级的转换和操作。
            这里右边不会取到compVec.begin()+k

            在 C++ 中，std::transform 不会自动调整输出容器的大小。它假设输出容器已经有足够的
            空间来存放所有的结果。如果输出容器的大小不足以存放所有结果，那么 std::transform
            会覆盖容器末尾之外的内存，这可能导致运行时错误，如内存访问违规（segmentation 
            fault）或其他形式的崩溃。所以这里ans必须初始化
            */
        });

        return ans;
    }
};

[GReyQT]

题解思路：

（1）使用哈希表存储数组nums中元素出现的频次； （2）因为unordered_map是无序的，因此将装换为可排序的vector<pair<int, int>> （3）降序排序，获取前k个；

代码：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        for (int i = 0; i < nums.size(); ++i) {
            cnt[nums[i]]++;
        }
        // 转换成 vector<pair<int, int>>
        vector<pair<int, int>> sorted_cnt(cnt.begin(), cnt.end());
        // 按照第二个元素降序排序
        sort(sorted_cnt.begin(), sorted_cnt.end(),
             [](const pair<int, int>& a, const pair<int, int>& b) {
                 return a.second > b.second;
             });
        vector<int> res;
        for (int i = 0; i < k; ++i) {
            res.push_back(sorted_cnt[i].first);
        }
        return res;
    }
};

复杂度分析：

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

[hillsonziqiu]

思路

使用hash表，遍历数组，每遇到一次一样的就+1，这样就有了key为元素，value为重复次数的map。 将这个map转换成为数组，然后进行sort排序，通过slice切割（或者设置length），获得排名前k的数组。最后再通过map方法转换成为输出的数组形式即可。

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  const timesMap = new Map();
  for (const num of nums) {
    if (timesMap.has(num)) {
      timesMap.set(num, timesMap.get(num) + 1);
    } else {
      timesMap.set(num, 1);
    }
  }

  // 迭代数组
  const generatorArr = [...timesMap];
  const result = generatorArr
    .sort((a, b) => {
      return b[1] - a[1];
    })
    .slice(0, k)
    .map((item) => item[0]);

  return result;
};

复杂度分析

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

[atom-set]

思路

• 遍历数组，记录数组中元素出现的次数存放到哈希表
• 对哈希表中的 val 进行排序
• 取出排序后的前 k 个元素，然后去哈希表查询的 key

代码

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
  var hash1 = new Map();
  var resArr = [];
  var dist = [];
  for (var i = 0; i < nums.length; i++) {
    if (hash1.has(nums[i])) {
      hash1.set(nums[i], hash1.get(nums[i]) + 1);
    } else {
      hash1.set(nums[i], 1);
    }
  }

  for (var [k1, v1] of hash1.entries()) {
    resArr.push(v1);
  }

  // 排序
  resArr = resArr.sort((a, b) => {
    return a - b > 0 ? -1 : 1;
  });
  for (var j = 0; j < k; j++) {
    for (var [k2, v2] of hash1.entries()) {
      if (v2 === resArr[j]) {
        dist.push(k2);
        hash1.set(k2, 0);
      }
    }
  }
  return dist;
};

复杂度分析

• 时间复杂度: O(N^2)
• 空间复杂度: O(N)