目录
大堆
小堆
vector+sort
vector+stable_sort
multimap
set/multiset
与GPT的对话
1.对于比较类型中 < 运算符重载的理解
2.map有稳定性的说法吗
编辑
3.为什么map和set类的仿函数后面要加const来修饰*this
5.关于名词的理解
6.匿名对象对类要求
7.map和set的基本知识
分析：其实就是选择一种容器排序，需要能够存放一对元素，可以想到使用map，unordered_map，vector，pair
堆：
个人理解：比较的时候左边是parent，右边是child，所以当仿函数是小于号时候，也就是孩子大，接下来进行交换，大的自然往就上走；对于一般的线性结构小于升序，大于降序，我觉得是这样的nums[right]<nums[left]
大堆
可以建大堆，也可以小堆
1.大堆，就是大的在根，这样的话就不能建立一个大小为K的堆，只能全部梭哈
2. 比较逻辑是根据题意来的，个数优先，其次在个数相同的时是字典序，所以肯定有个或（“ | | ”）
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& kv1, const PSI& kv2)
{
return kv1.second < kv2.second || kv1.second == kv2.second
&& kv1.first > kv2.first;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m;
for(auto& e : words)
m[e]++;
priority_queue<PSI, vector<PSI>, cmp> heap(m.begin(), m.end());
vector<string> ret;
for(int i = 0; i < k; i++)
ret.push_back(heap.top().first), heap.pop();
return ret;
}
};小堆
1.如果堆里的K个元素就是符合条件的，那么只能小根堆；遇到新的元素先push进来，如果size() > K那么就pop()
2.在输出方面：因为只能取出堆顶元素，如果选择正着存，可以使用ret.push_back() + reverse
如果是想一步到位那么就放到对应的下标里，注意：需要提前开空间初始化（也就是赋值），因为单单开空间是不能使用下标来访问元素（其实是很有道理的，没有初始化这个数据就是不属于你，就是不应该有访问权限，可是我是修改这个位置的值，不是访问啊；修改的前提是有访问的权限，有访问权限才有修改资格），可以使用resize或者创建对象的时候就初始化
3.cmp与大堆相反
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& kv1, const PSI& kv2)
{
return kv1.second > kv2.second || kv1.second == kv2.second
&& kv1.first < kv2.first;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m;
for(auto& e : words)
m[e]++;
priority_queue<PSI, vector<PSI>, cmp> heap;
for(auto& e : m)
{
heap.push(e);
if(heap.size() > k) heap.pop();
}
// vector<string> ret(k);
// for(int i = k - 1; i >= 0; i--)
// ret[i] = heap.top().first, heap.pop();
vector<string> ret;
for(int i = 0; i < k; i++)
ret.push_back(heap.top().first), heap.pop();
reverse(ret.begin(), ret.end());
return ret;
}
};vector+sort
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& kv1, const PSI& kv2)
{
return kv1.second > kv2.second || kv1.second == kv2.second
&& kv1.first < kv2.first;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> count_map;
for(auto& v : words)
count_map[v]++;
vector<pair<string, int>> v(count_map.begin(), count_map.end());
sort(v.begin(), v.end(), cmp());
vector<string> ret;
for(int i = 0; i < k; i++)
ret.push_back(v[i].first);
return ret;
}
};vector+stable_sort
稳定性指的是元素在原始序列中的相对顺序，这里不需要写个数相同情况下字典序的比较，是因为map默认就是less<key>，如果掉默认的greater()，那么遇到比较时传的是pair的运算符重载
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& kv1, const PSI& kv2)
{
return kv1.second > kv2.second;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> count_map;
for(auto& v : words)
count_map[v]++;
vector<pair<string, int>> v(count_map.begin(), count_map.end());
stable_sort(v.begin(), v.end(), cmp());
vector<string> ret;
for(int i = 0; i < k; i++)
ret.push_back(v[i].first);
return ret;
}
};multimap
1. 不熟练->写出这样的map<pair<string, int>, cmp>类型，导致下面push_back报错（没有匹配的函数）,那么也就不能用map的迭代器了，类型不配了
2. 
cmp传的参数只能是第一次参数，所以int必须在string前面，那么为什么保证了字典序？我觉得是因为第一个map
问题:会发现仿函数后面有const，前面的容器为什么不需要?map和set就要？
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const int key1, const int key2) const
{
return key1 > key2;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> count_map;
for(auto& str : words)
count_map[str]++;
// map<pair<string, int>, cmp> sort_map(count_map.begin(), count_map.end());
// multimap<string, int, cmp> sort_map(count_map.begin(), count_map.end());
// multimap<int, string, cmp> sort_map(count_map.begin(), count_map.end());
multimap<int, string, cmp> sort_map;
for(auto& e : count_map)
sort_map.insert({e.second, e.first});
// sort_map.insert(make_pair(e.second, e.first));
vector<string> ret;
auto it = sort_map.begin();
for(int i = 0; i < k; i++)
{
ret.push_back(it->second);
it++;
}
return ret;
}
};set/multiset
map和set的取值只能通过迭代器
这个地方的multiset和set效果是一样的，因为每一pair都是不一样的
class Solution {
public:
typedef pair<string, int> PSI;
struct cmp
{
bool operator()(const PSI& kv1, const PSI& kv2) const
{
return kv1.second > kv2.second || kv1.second == kv2.second && kv1.first < kv2.first;
}
};
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> count_map;
for(auto& str : words)
count_map[str]++;
set<PSI, cmp> sort_set(count_map.begin(), count_map.end());
//multiset<PSI, cmp> sort_set(count_map.begin(), count_map.end());
vector<string> ret;
auto it = sort_set.begin();
for(int i = 0; i < k; i++)
{
ret.push_back(it->first);
it++;
}
return ret;
}
};与GPT的对话
1.对于比较类型中 < 运算符重载的理解
升序是less，重载的是 < (小于号)
2.map有稳定性的说法吗
3.为什么map和set类的仿函数后面要加const来修饰*this
我没怎么看懂，以现在的功力只能记住map和set中的比较类型的()运算符重载的成员函数，需要加上const
5.关于名词的理解
6.匿名对象对类要求
7.map和set的基本知识
