题目链接:https://leetcode-cn.com/problems/top-k-frequent-elements/

题解

该题的目的很简单,考察是堆排序,就是将遍历所有的元素,用一个hashmap记录所有出现元素的频数,最后从hashmap导出来一个个 < 数字,频数> 的元组,最后通过比较频数来获取最高频的几个元素,这样想想,用快排也不是不行的

还是谈谈根排序吧,题目中要求的是前几个高频元素,那么我们就应该使用大根堆一个一个把数据拿出来?

Naive!

题目中给到了提示:

你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。

如果你执行K次大根堆排序,那么时间复杂度不会优于 O(n log n) 。

那么可以反其道行之,使用小根堆。

如果使用小根堆,根元素是堆中最小值,那么,我们只需要固定住小根堆中的元素最大为K,并在向堆中插入元组(元素)的过程中执行以下操作:

  1. 如果堆内元素数没有达到K,则直接插入;
  2. 如果堆内元素数已经达到K,只需要比较根元素,此时:
  • 如果根元素的频数大于待插入的元素,直接忽略掉待插入的元素。
  • 如果根元素的频数小于待插入的元素,那么可以拿掉这个根元素,再将待插入的元素插入到堆中。

最后,当所有元组处理完毕后,则可以输出所有堆内的元素了,答案就是它们。

垃圾代码

class Solution {
public:
    unordered_map<int,int> heap;
    
    static bool cmp(pair<int,int> & a, pair<int,int> &b){
        return a.second > b.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> ans;
        if (k == 0 || nums.size() == 0){
            return ans;
        }
        for (int i = 0 ; i < nums.size() ; ++i){
            heap[nums[i]] += 1;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(&cmp)> queue(cmp);
        
        for (auto it = heap.begin(); it != heap.end(); ++it){
            if (queue.size() < k){
                queue.push(*it);
            }else{
                if (queue.top().second < it->second){
                    queue.pop();
                    queue.push(*it);
                }
            }
        }

        while(!queue.empty()){
            ans.push_back(queue.top().first);
            queue.pop();
        }

        


        // vector<pair<int,int>> nodes;
        // for (auto it = heap.begin(); it != heap.end(); ++it){
        //     nodes.push_back(*it);
        // }
        // for(int i = 0 ; i < k ; ++ i){
        //     getMaxOne(nodes);
        //     ans.push_back(nodes[0].first);
        //     nodes.erase(nodes.begin());
        // }
        return ans;
    }


    

    void getMaxOne(vector<pair<int,int>>& nodes){

        int size = nodes.size();
        int p = size / 2 - 1;

        while (p >= 0 && p < size){
            
            if (p * 2 + 1 < size && nodes[p].second < nodes[2 * p + 1].second) {
              
                swap(nodes[p],nodes[2*p+1]);
               
                if ((2 * (p * 2 + 1) + 2< size && nodes[p * 2 + 1].second < nodes[ 2 * (p * 2 + 1) + 2].second) 
                ||  ( 2 * (p * 2 + 1) + 1 < size && nodes[p * 2 + 1].second < nodes[ 2 * (p * 2 + 1) + 1].second)){
                    getMaxOne(nodes);
                }
            }

            if (p * 2 + 2 < size && nodes[p].second < nodes[p * 2 + 2].second) {
                
                swap(nodes[p],nodes[p * 2 + 2]);
               
                if ((2 * (p * 2 + 2) + 2< size && nodes[p * 2 + 2].second < nodes[ 2 * (p * 2 + 2) + 2].second) 
                ||  ( 2 * (p * 2 + 2) + 1 < size && nodes[p * 2 + 2].second < nodes[ 2 * (p * 2 + 2) + 1].second)){
                    getMaxOne(nodes);
                }
            }

            p--;

        }
    }

};