leetcode 347 前K个高频元素

ゝ一纸荒年。 2022-09-11 04:11 138阅读 0赞

## 前言 ##

题目：[347. 前K个高频元素][347. _K]

参考题解：[前K个高频元素-力扣官方题解][K_-]

--------------------

## 提交代码 ##

求前k大个元素，这是老生常谈的问题。

### 暴力解法 ###

非降序排序，前k个元素，即为前k大的元素。比较排序，时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn)。

class Solution {
    private:
        struct cmp{
            bool operator() (const pair<int,int>& p1,const pair<int,int>& p2){
                // 使用键值对的值进行降序排序
                return p1.second>p2.second;
            } 
        };
    
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            // const int len = nums.size();
            // assert(len>=k);
    
            // 统计频率
            map<int,int> statisFreqMap;
            for( int num : nums)
                statisFreqMap[num]++;
            
            // 将统计结果放入vector中，按照频率进行降序排序
            vector<pair<int,int>> statisFreqVec;
            map<int,int>::iterator it=statisFreqMap.begin();
            for(it; it!=statisFreqMap.end(); it++){
                statisFreqVec.push_back(make_pair(it->first,it->second));
            }
            sort(statisFreqVec.begin(),statisFreqVec.end(),cmp());
    
            // 输出频率最高的前k个元素
            vector<int> result;
            for(int i=0; i<k; i++){
                result.push_back(statisFreqVec[i].first);
            }
    
            return result;
        }
    };

### 堆排序 ###

我们不需要维护所有元素的顺序，只需要维护前k大的元素。如果做过[leetcode 239 滑动窗口的最大值][leetcode 239],必然知道**堆可以动态维护最大值**。

思路：维护一个k个元素的小顶堆。预先插入k个元素到小顶堆中。之后每次插入一个元素，再删除堆顶。

时间复杂度为 O ( n l o g k ) O(nlogk) O(nlogk)。

#include <vector>
    #include <map>
    #include <algorithm>
    #include <cassert>
    #include <queue>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    private:
        struct cmp{
            bool operator() (const pair<int,int>& p1,const pair<int,int>& p2){
                // 使用键值对的值进行降序排序
                return p1.second>p2.second;
            } 
        };
    
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
            // const int len = nums.size();
            // assert(len>=k);
    
            // 统计频率
            map<int,int> statisFreqMap;
            for( int num : nums)
                statisFreqMap[num]++;
            
            // 小顶堆，遍历过程中，维护前k大个元素
            priority_queue<pair<int,int>,vector<pair<int,int>>,cmp> freqQueue; 
            map<int,int>::iterator it = statisFreqMap.begin();
    
            // 预放置前k个元素
            for(int i=0; i<k; i++){
                freqQueue.push(make_pair(it->first,it->second));
                it++;
            }
    
            // 向小顶堆中插入一个元素，再删除堆顶最小的元素
            for(int i=k; i<statisFreqMap.size(); i++){
                freqQueue.push(make_pair(it->first,it->second));
                it++;
                freqQueue.pop();
            }
    
            // 将前k大个元素输出
            vector<int> result;
            while(!freqQueue.empty()){
                result.push_back(freqQueue.top().first);
                freqQueue.pop();
            }
            reverse(result.begin(),result.end()); 
    
            return result;
        }
    };
    
    int main(void){
        vector<int> nums = {3,2,3,1,2,4,5,5,6,7,7,8,2,3,1,1,1,10,11,5,6,2,4,7,8,5,6};
        int k = 10;
        Solution s;
        vector<int> result = s.topKFrequent(nums,k);
        for(int num : result)
            cout<<num<<" ";
    }

上面这个代码可以改进。即，每次不直接插入。可以拿当前元素和堆顶元素进行比较。若堆顶元素较大，直接舍弃当前元素。若堆顶元素较小，删除堆顶元素，再插入新元素。

### 快速排序 ###

原版的快速排序算法的平均时间复杂度为  O ( n l o g n ) O(nlogn) O(nlogn)。我们的算法中，每次只需在其中的一个分支递归即可，因此算法的平均时间复杂度降为 O ( n ) O(n) O(n)。

我以前敲过[排序算法的代码][Link 1]。这个算法写起来有些费劲，这里复制下参考题解中的代码。详细见参考题解。

class Solution {
    public:
        void qsort(vector<pair<int, int>>& v, int start, int end, vector<int>& ret, int k) {
            // 随机选择一个哨兵，将其置换到开头位置
            int picked = rand() % (end - start + 1) + start;
            swap(v[picked], v[start]);
    
            // 双指针。start为哨兵。(start,index]为大于哨兵的值。(index,i)为小于哨兵的值。i为当前待比较的数。(i,end]为后续比较的数。
            int pivot = v[start].second;
            int index = start;
            for (int i = start + 1; i <= end; i++) {
                if (v[i].second >= pivot) {
                    swap(v[index + 1], v[i]);
                    index++;
                }
            }
            // 把哨兵置换到中间
            swap(v[start], v[index]);
    
            // 多退少补
            if (k <= index - start) { // if (k < index-start+1)
                qsort(v, start, index - 1, ret, k);
            } else {
                for (int i = start; i <= index; i++) {
                    ret.push_back(v[i].first);
                }
                if (k > index - start + 1) { // if (k != index-start+1)
                    qsort(v, index + 1, end, ret, k - (index - start + 1));
                }
            }
        }
    
        vector<int> topKFrequent(vector<int>& nums, int k) {
            unordered_map<int, int> occurrences;
            for (auto& v: nums) {
                occurrences[v]++;
            }
    
            vector<pair<int, int>> values;
            for (auto& kv: occurrences) {
                values.push_back(kv);
            }
            vector<int> ret;
            qsort(values, 0, values.size() - 1, ret, k);
            return ret;
        }
    };

[347. _K]: https://leetcode-cn.com/problems/top-k-frequent-elements/
[K_-]: https://leetcode-cn.com/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode-solution/
[leetcode 239]: https://blog.csdn.net/sinat_38816924/article/details/120244483
[Link 1]: https://github.com/da1234cao/data_structure/tree/master/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA/%E7%AC%AC%E4%BA%8C%E9%83%A8%E5%88%86_%E6%8E%92%E5%BA%8F%E5%92%8C%E9%A1%BA%E5%BA%8F%E7%BB%9F%E8%AE%A1%E9%87%8F