LeetCode刷题笔记（Top K Frequent Elements）

刚刷了一道难度适中的题目，可能由于好久都没刷题了的缘故，在代码书写方面明显略显生疏，所以大家一定不要长时间不写代码啦，加油！

题目如下：

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

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

You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

题意分析：

给定一个非空整数数组nums和一个整数k，请返回数组中出现频率最高的前k个元素。

解答如下：

方法一（优先队列(最小堆实现)）

① 先创建一个哈希表record_freq用于统计各数字出现的频率；

② 再创建一个优先队列pq，用于将频率出现最高的k个元素存储起来；

③ 最后创建一个res向量存放优先队列pq的遍历结果。

注：优先队列只能第一位存频率，第二位存元素，反之不行，笔者认为之所以这样是因为优先队列应该是拿第一位的值进行比较大小。

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

        //哈希表的第一位存元素，第二位存频率，目的在于统计各数字出现的频率
        unordered_map<int, int> record_freq;
        for( int i = 0; i < nums.size(); i++ ){
            record_freq[nums[i]]++;
            }

            //优先队列的第二位存元素，第一位存频率，目的在于将频率出现最高的k个元素存储起来
            priority_queue < pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
            for ( unordered_map<int, int>::iterator iter = record_freq.begin(); iter != record_freq.end(); iter++ ){
                if( pq.size() == k ){
                    //比较频率，若哈希表中元素的频率大于优先队列中的频率最小的元素，则更新优先队列
                     if( pq.top().first < iter -> second ){
                        pq.pop();
                        pq.push( make_pair( iter -> second, iter -> first ));}}
                else
                    //直接更新优先队列
                    pq.push( make_pair( iter -> second, iter -> first ));
            }
            //遍历频率出现最高的k个元素，并存放在res中
            vector<int> res;
            while( !pq.empty() ){
                res.push_back( pq.top().second );
                pq.pop();
            }
          return res;
        }
    };

提交后的结果如下：

 

 

 

方法二（优先队列(最大堆实现)）

① 先创建一个哈希表record_freq用于统计各数字出现的频率；

② 再创建一个优先队列pq，用于将各元素按照出现频率从高到低存储起来；

③ 最后创建一个res向量，遍历优先队列pq，取出前k个元素（即频率出现最高的前k个元素）并存放在res中。

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

        //哈希表的第一位存元素，第二位存频率，目的在于统计各数字出现的频率
        unordered_map<int, int> record_freq;
        for( int i = 0; i < nums.size(); i++ ){
            record_freq[nums[i]]++;
        }

        //优先队列的第二位存元素，第一位存频率，目的在于将各元素按照出现频率从高到低存储起来
        priority_queue < pair<int,int> > pq;
        for ( unordered_map<int, int>::iterator iter = record_freq.begin(); iter != record_freq.end(); iter++ )
            pq.push( make_pair( iter -> second, iter -> first ));

        //遍历优先队列，取出前k个元素（即频率出现最高的前k个元素）并存放在res中
        vector<int> res;
        for(int i = 0; i < k; i++){
            res.push_back( pq.top().second );
            pq.pop();
        }
        return res;
    }
};

提交后的结果如下：

 

日积月累，与君共进，增增小结，未完待续。