LeetCode347 K Frequent Elements 的一点问题

Question

波波老师，我在做第6章队列的347题时，在使用优先队列之外，尝试了下直接对unordered_map统计后的值的频率进行排序，其中的cmp函数如果不设为静态函数的话，就会报错，这是为什么呢?
代码如下：
class Solution {

static int cmp( const pair<int,int>& x, const pair<int,int>& y) {
return x.second > y.second;
}
public:
// 1. Sort the Value of map
vector topKFrequent(vector& nums, int k) {

    assert( k > 0);
    unordered_map<int,int> freq;
    // get the frequency of each element
    for( int i=0; i<nums.size(); ++i)
        freq[ nums[i]] ++;

    assert( k <= freq.size());
    vector< pair<int,int> > record;
    auto iter = freq.begin();
    for( ; iter != freq.end(); ++iter)
        record.push_back( make_pair( iter->first, iter->second));
    sort( record.begin(), record.end(), cmp);

    vector<int> res;
    for( int i=0; i<k; ++i)
        res.push_back( record[i].first);

    return res;
}

}

Answer 1

liuyubobobo 2019-03-14 03:18:02

如果不写static，说明cmp是一个成员函数。成员方法的意思是，他必须依附于一个类对象进行调用，而不能单独调用。

现在，你将这个成员方法cmp传给sort，sort已经脱离了Solution类的控制域了，soert并没有途径获得Solution这个类的信息，也就不会理解Solution这个类里面的某个成员方法是怎么回事。而使用static，将cmp这个方法设置成全局的，而不仅仅是绑定在Solution类内部的。

另一个解决方案是，单独声明cmp，让cmp完全和Solution无关。（C++是面向对象和面向过程混编的语言。这一点和Java不一样。）

// 单独声明cmp，让cmp和Solution类无关
int cmp( const pair<int,int>& x, const pair<int,int>& y) {
    return x.second > y.second;
}

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        assert( k > 0);
        unordered_map<int,int> freq;
        // get the frequency of each element
        for( int i=0; i<nums.size(); ++i)
            freq[ nums[i]] ++;
        assert( k <= freq.size());
        vector< pair<int,int> > record;
        auto iter = freq.begin();
        for( ; iter != freq.end(); ++iter)
            record.push_back( make_pair( iter->first, iter->second));
        sort( record.begin(), record.end(), cmp);
        vector<int> res;
        for( int i=0; i<k; ++i)
            res.push_back( record[i].first);
        return res;
    }
};

个人认为更优雅的解决方案是使用lambda表达式：）

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        assert( k > 0);
        unordered_map<int,int> freq;
        // get the frequency of each element
        for( int i=0; i<nums.size(); ++i)
            freq[ nums[i]] ++;
        assert( k <= freq.size());
        vector< pair<int,int> > record;
        auto iter = freq.begin();
        for( ; iter != freq.end(); ++iter)
            record.push_back( make_pair( iter->first, iter->second));
        
        // 使用lambda表达式定制sort中的cmp
        sort(record.begin(), record.end(), 
             [](const pair<int,int>& x, const pair<int,int>& y){
                 return x.second > y.second;
             });
        vector<int> res;
        for( int i=0; i<k; ++i)
            res.push_back( record[i].first);
        return res;
    }
};

如果对这个语法不熟悉，可以在网上搜索相关资料自学一下：）

继续加油！：）

• 提问者 碳晚揽月 #1

  好的，谢谢bobo老师！

Answer 2

提问者 碳晚揽月 2019-03-14 02:19:56

另外在b站发现有人上传了您的课程盗版视频

https://www.bilibili.com/video/av44907624/?p=1

• liuyubobobo #1

  谢谢你提供的信息：）