[C++知识库]C++的排序实现

以这道题目为例，leetcode-692

一、用优先队列

// 写法1，用lambda表达式
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (auto& word : words) {
            cnt[word]++;
        }
		// 用lambda表达式写排序，需要配合使用decltype
        auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };
        priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
        for (auto& it : cnt) {
            que.push(it);
            if (que.size() > k) {
                que.pop();
            }
        }
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = que.top().first;
            que.pop();
        }
        return ret;
    }
};


// 写法2，实现排序函数，不对，会出现错误提示：template argument for template type parameter must be a type
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (auto& word : words) {
            cnt[word]++;
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> que(cmp);
        for (auto& it : cnt) {
            que.push(it);
            if (que.size() > k) {
                que.pop();
            }
        }
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = que.top().first;
            que.pop();
        }
        return ret;
}
// 这样写排序不对
    static bool cmp(const pair<string, int>& a, const pair<string, int>& b) {
        return a.second == b.second ? a.first < b.first : a.second > b.second;
    }
};


// 写法3，结构体重载operator
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> cnt;
        for (auto& word : words) {
            cnt[word]++;
        }
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> que;
        for (auto& it : cnt) {
            que.push(it);
            if (que.size() > k) {
                que.pop();
            }
        }
        vector<string> ret(k);
        for (int i = k - 1; i >= 0; i--) {
            ret[i] = que.top().first;
            que.pop();
        }
        return ret;
}
// 结构体重载operator实现排序，不需要使用decltype
    struct cmp {
        bool operator() (const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        }
    };
};


二、就用vector排序（三种方法都行）
// 写法1 ，lambda表达式
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> count;
        // 统计频率
        for(string& word : words) {
            count[word]++;
        }
        // 把map表存入vector中
        vector<pair<string, int>> res(count.begin(), count.end());
        // lambda表达式进行排序
         auto compare = [](const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        };

        sort(res.begin(), res.end(), compare);
        vector<string> ans;
        // 保存最终结果
        for(int i = 0; i < k; i ++) {
            ans.push_back(res[i].first);
        } 
        return ans;
    }
};



// 写法2，实现排序函数
bool compare(const pair<string, int>& s1, const pair<string, int>& s2) {
    // 频率相等，按字母排序
    if(s1.second == s2.second) return s1.first < s2.first;
    // 按照频率排序
    else return s1.second > s2.second;
}

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> count;
        // 统计频率
        for(string& word : words) {
            count[word]++;
        }
        // 把map表存入vector中
        vector<pair<string, int>> res(count.begin(), count.end());
        // 按照自定义排序函数进行排序
        sort(res.begin(), res.end(), compare);
        vector<string> ans;
        // 保存最终结果
        for(int i = 0; i < k; i ++) {
            ans.push_back(res[i].first);
        } 
        return ans;
    }
};

// 写法3，结构体重载operator
class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> count;
        // 统计频率
        for(string& word : words) {
            count[word]++;
        }
        // 把map表存入vector中
        vector<pair<string, int>> res(count.begin(), count.end());
		// 这里需要加括号
        sort(res.begin(), res.end(), compare());
        vector<string> ans;
        // 保存最终结果
        for(int i = 0; i < k; i ++) {
            ans.push_back(res[i].first);
        } 
        return ans;
    }

    struct compare {
        bool operator() (const pair<string, int>& a, const pair<string, int>& b) {
            return a.second == b.second ? a.first < b.first : a.second > b.second;
        }
    };

};