9.28 堆排序

首先，最重要的还是复习、复习、复习

堆排序，也是一种思想，遇到类似题目求解TopK的时候都可以先想到堆排序。

堆排序分大堆顶和小堆顶

升序----使用大顶堆

降序----使用小顶堆

这篇文章写的比较清楚：https://www.cnblogs.com/lanhaicode/p/10546257.html

题目：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

思路应该都有，具体就是实现的方法
1、利用map统计字符出现个数
2、按照个数排序
3、提出前K个

// 时间复杂度：O(nlogk)
// 空间复杂度：O(n)
class Solution {
public:
    // 小顶堆
    class mycomparison {
    public:
        bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
            return lhs.second > rhs.second;
        }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 要统计元素出现频率
        unordered_map<int, int> map; // map<nums[i],对应出现的次数>
        for (int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }

        // 对频率排序
        // 定义一个小顶堆，大小为k
        priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que;

        // 用固定大小为k的小顶堆，扫面所有频率的数值 
        for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) {
            pri_que.push(*it);
            if (pri_que.size() > k) { // 如果堆的大小大于了K，则队列弹出，保证堆的大小一直为k
                pri_que.pop();
            }
        }

        // 找出前K个高频元素，因为小顶堆先弹出的是最小的，所以倒叙来输出到数组
        vector<int> result(k);
        for (int i = k - 1; i >= 0; i--) {
            result[i] = pri_que.top().first;
            pri_que.pop();
        }
        return result;

    }
};

另外STL 最大堆、最小堆的应用可以看https://blog.csdn.net/my_lovely_lemon_tree/article/details/78007316

operator用法可以看https://blog.csdn.net/woxiaohahaa/article/details/53191247

c++ map与unordered_map区别及使用https://blog.csdn.net/qq_21997625/article/details/84672775

::iterator it 属于C++的迭代器，常用*it来访问元素
https://blog.csdn.net/u010112268/article/details/81111086

现在需要考虑毕业问题，还有考虑工作问题，很焦虑。感觉刷题到现在好像没有什么起色，机械的背一些东西，经不起深挖。整个论文架构还没有想好，真的要提升效率了。以前总是想的太多，做的太少。没有目标的话，做事就是一盘散沙。
现在秋招还要继续找，但是也要持续到春招。希望能够有一个好结果。顺利毕业，找到可心的工作。
越长大似乎越能看清楚自己的上限，有时候总在想，我的选择是正确的么，我以后的生活似乎已经被预见到了。但还是总想着拼一把，我好像是那种能力匹配不上抱负的人吧。我不会放弃的，我需要的应该是计划、方法、努力。
日常打气，加油