leetcode学习记录_k个数

这种题目通常都是和堆（优先队列）以及快速选择有关，请刻进DNA里…

347. 前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

先来个简单的思路，数组+自定义排序，当然，用上排序的时候就不满足题目进阶要求的O(n log n)了，因为排序的时间复杂度至少也得O(n log n)，根本没优于O(n log n)，但还是记录一下方法

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>map;
        for(int&num : nums)//遍历数组的时候把出现频次填入哈希表
        ++map[num];
        vector<pair<int,int>>buf;
        buf.reserve(nums.size());
        for(auto&temp : map)
        {
            buf.push_back({temp.first,temp.second});
        }
        sort(buf.begin(),buf.end(),//按出现频次的降序排序
        [](pair<int, int>&a,pair<int, int>&b){return a.second>b.second;});
        vector<int>res(k);
        for(int i = 0;i<k;++i)
        {//因为是降序排序，所以直接输出前k个就好
            res[i] = buf[i].first;
        }
        return res;
    }
};

然后就是优先队列，其实C++的优先队列的底层也是堆实现的

说说优先队列的思路
和为什么使用优先队列时间复杂度能达到能优于O(n log n)达到O(n log k)

优化：
不管是优先队列，还是排序法，内部都是排序，如果维护一个完整的（长度为n）优先队列，时间复杂度也是O(n log n)，但是我们只需要k个，因此我们维护长度最大为k的优先队列，时间复杂度就能降低为O(n log k)
思路：
维护一个降序的优先队列（小顶堆），为什么是降序不能是升序？这就得反过来思考了，我们要留下k个最大的，就得舍弃n-k个最小的，因为是队列，我们只能访问根节点，同时还要维护长度为k，即代表需要进行删除的操作，如果是大顶堆，我们发现下一个数值比当前根节点大，那我们要删除根节点吗？明显不能啊，因为好歹现在的根节点也是堆中最大的数字，要删也只能删堆中最小的数字，才能保证不会出错，
于是用小顶堆不就完事了嘛，如果当前数字比根节点的数字大，那就舍弃根节点，然后把当前数字放入堆中

class Solution {
    struct cmp
    {
        bool operator()(pair<int ,int>&a,pair<int ,int>&b)
        {//自定义的比较规则，因为这里的排序是pair，不是基本数据类型
            return a.second>b.second;//让队列按降序
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>map;
        for(int&num : nums)
        ++map[num];//将元素和频次填入哈希表
        //定义一个按频次降序排序的优先队列
        priority_queue<pair<int ,int>,vector<pair<int ,int>>,cmp>que;
        for(auto&temp:map)
        {
            if(que.size()==k)//维护队列的长度最大为k
            {//因为是按降序排的，所以top是最小的，如果有比top大的，就删除top，添加这个新的进去
            //这里的删除操作别忘了，不然就和排序法一样了，因为一直维护着长度为k
            //才能让时间复杂度为Nlog(k)而不是排序的Nlog(N)
                if(que.top().second<temp.second)
                {
                    que.pop();
                    que.emplace(temp);
                }
            }
            else
            {
                que.emplace(temp);
            }
        }
        vector<int>res;
        res.reserve(k);
        while(!que.empty())
        {
            res.emplace_back(que.top().first);
            que.pop();
        }
        return res;
    }
};

当然还有快速排序的版本，基于随机选取的快速排序平均时间复杂度为O(n)，超快哦，而且也很好写（只要你会快排）
快排…我的超人…

快速排序的原理，是通过比较和交换，把比key大的全交换到右边（升序），比key小的全部交换到左边，这样key就摆放到了最合适的位置：即有序序列中它应该在的位置

对于这一题，我们只要用快排对出现频率进行排序，一旦发现排完序后的key下标是size-k-1，就return，不要继续递归的排序了，其他事情和我们没关系，因为比key大的k个数字已经排到了key后面了，这k个数字就是题目要求的数字，而且题目也说不需要按顺序，所以直接提取数字，返回就完事了

唯一麻烦点的就是各种容器的转换了，先用哈希表计数，再转成数组vector<pair<int,int>>，再以pair.second为依据进行排序，然后在提取pair.first组成新的数组，再返回

代码：

class Solution {
    int val;
    int partition(vector<pair<int,int>>& nums, int L, int R)
    {
        int keyIdx = (rand()%(R-L+1))+L;
        swap(nums[keyIdx],nums[L]);
        int key = nums[L].second;
        while(L <R)
        {
            while(L <R&&nums[R].second>=key)--R;
            swap(nums[L],nums[R]);
            while(L <R&&nums[L].second<=key)++L;
            swap(nums[L],nums[R]);
        }
        return L;
    }
    void QSort(vector<pair<int,int>>& nums, int L, int R)
    {
        if(L >= R)return;
        int idx = partition(nums,L,R);
        if(idx==val)return;
        else if(idx<val) QSort(nums,idx+1,R);
        else if(idx>val) QSort(nums,L,idx-1);
    }
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        srand(time(NULL));
        unordered_map<int,int>map;
        for(int&num:nums)++map[num];
        vector<pair<int,int>>res;
        for(auto&buf:map)res.push_back(buf);
        val = res.size()-k-1;
        QSort(res, 0, res.size()-1);
        vector<int>ret;
        for(int idx = res.size()-1;idx>val;--idx)
        {
            ret.push_back(res[idx].first);
        }
        return ret;
    }
};

随机的速度，还是很快的，不过一切随机就是了，哈哈

215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

来源：力扣（LeetCode）
同样是k个数的题目，思路也很像，而且这一题根本不需考虑重复项，直接对数组进行排序，后，取nums[size-k]即可

当然，直接排序是最后的手段，我们还有优化的余地，那就是利用快速排序的原理：把数字放在该放的地方，于是我们在进行快速排序的时候，判断一下，这个所谓的正确位置是不是size-k，如果是直接返回，不需要后序的递归了，我们根本不在乎整个数组是不是有序，我们只在乎size-k这个位置，而且改起来也很简单，只需要改3处，简单快速

如果不懂快速排序的可以看看这里👉

这里的快速排序是基于随机选取的快速排序

代码：

class Solution {
    int num;
    int Partition(vector<int>& nums,int L, int R)
    {
        int keyIdx = (rand()%(R-L+1))+L;
        swap(nums[keyIdx],nums[L]);
        int key = nums[L];
        while(L < R)
        {
            while(L < R && nums[R]>=key)--R;
            swap(nums[L],nums[R]);
            while(L < R && nums[L]<=key)++L;
            swap(nums[L],nums[R]);
        }
        return L;
    }
    void QSort(vector<int>& nums,int L, int R)
    {
        if(L >= R) return ;
        int idx = Partition(nums, L, R);
        if(idx == num) return;//判断是否是我们想要的位置
        else if(idx > num) QSort(nums, L, idx-1);//只需修改这两行就ok
        else if(idx < num) QSort(nums, idx+1, R);//
        //QSort(nums, L, idx-1);
        //QSort(nums, idx+1, R);
    }
    void QuickSort(vector<int>& nums)
    {
        QSort(nums, 0, nums.size()-1);
    }
public:
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        num = nums.size()-k;
        QuickSort(nums);
        return nums[num];
    }
};

692. 前K个高频单词

给一非空的单词列表，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率，按字母顺序排序。

示例 1：

输入: [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”,> “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/top-k-frequent-words

这题也没啥新意，这里讲这题的原因主要是为了介绍几个api，当然，都是快速选择的

前面几题我都在自己写快排，如果条件允许的话，还是调api比较爽啊

nth_element

partial_sort

看看参数列表：（两者都是一样的）

( Iterator first, Iterator middle, Iterator last);

(Iterator first, Iterator middle, Iterator last, Compare comp);

nth_element 是快速选择，
根据排序规则快出选出在middle处的元素，规则默认升序，也可以自定义，当然底层是快速排序，所以，middle两边的元素都大于或小于middle

partial_sort则是在nth_element的基础上在升级了一下，局部排序，当然不是那种肤浅的局部排序，而是将局部的元素按照完全排序的样子摆放好

当然，也可以用nth_element+sort达成partial_sort，或者说，有时候不得不用，因为partial_sort只能局部排序first到middle区间的元素，后半部分就需要自己sort了，当然或许有其他api，不过我也没研究那么深

调用这些api的话，加上lambda表达式的自定义排序，即可简单快速的完成这些题目

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        using PSI = pair<string, int>;
        unordered_map<string, int>map;
        for(int i = 0;i<words.size();++i){//哈希表记录单词以及出现次数
            ++map[words[i]];
        }
        vector<pair<string, int>>ans;
        for(auto&temp:map){//将单词以及频次填入数组
            ans.emplace_back(temp);
        }
        auto cmp = [](const PSI&p1, const PSI&p2){//根据题意定义排序规则
            if(p1.second == p2.second)
                return p1.first<p2.first;
            else
                return p1.second>p2.second;
        };
        partial_sort(ans.begin(), ans.begin()+k, ans.end(), cmp);//一句搞定
        vector<string>res;
        for(int i = 0;i<k;++i){//填入单词
            res.emplace_back(ans[i].first);
        }
        return res;
    }
};

当然还有堆排序的写法，虽然我更喜欢用快速选择，不过该会的还是得会

前面得写法为了维护堆的size为k，我们各种判断，但是可以改变一下，前面的做法是不允许堆的size>k，这里的优化做法，允许堆的临时size为k+1，当然会pop掉多出来的一个
两种方法，我比较喜欢后者，写起来简单，看着也简单，但是效率会低一点点点点点，因为后续的插入需要在k个元素中插入，而前一种方法，最多也只需要在k-1个元素中插入，但是我觉得没必要，简单一点好

老办法，小顶堆，用结构体重载操作符的方式，这样比较好看，我喜欢用这种方式定义排序规则
不过这里注意一下，默认大顶堆的排序是降序哦，也很好理解，毕竟堆顶的是最大元素嘛，
这里我们要建立小顶堆，所以频次排序规则得升序，当然频次一样时：根据题意，字符的规则是降序

class Solution {
    using PSI = pair<string, int>;
    struct cmp{//重载运算符，改变排序规则
        bool operator()(PSI&p1, PSI&p2){
            if(p1.second==p2.second)
                return p1.first<p2.first;
            else
                return p1.second>p2.second ;
        }
    };
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int>map;
        for(int i = 0;i<words.size();++i){//记录频次
            ++map[words[i]];
        }
        priority_queue<PSI, vector<PSI>, cmp>minHeap;//建立小顶堆
        for(auto&temp:map){
            minHeap.push(temp);
            if(minHeap.size()>k)//这里就是简化的点了
            minHeap.pop();
        }
        vector<string>res(minHeap.size());//因为是小堆顶，所以反向赋值给数组
        for(int i = res.size()-1;i>=0;--i){
            res[i] = minHeap.top().first;
            minHeap.pop();
        }
        return res;
    }
};