LeetCode刷题笔记-数据结构-day20

男娘i 2023-10-01 17:06 10阅读 0赞

#### 文章目录 ####

*  LeetCode刷题笔记-数据结构-day20
 *   *  215. 数组中的第K个最大元素
     *   *  1.题目
         *  2.解题思路
         *  3.代码
     *  347. 前 K 个高频元素
     *   *  1.题目描述
         *  2.解题思路
         *  3.代码

## LeetCode刷题笔记-数据结构-day20 ##

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

#### 1.题目 ####

> 原题链接：[215. 数组中的第K个最大元素][215. _K]

![image-20220203093144515][]

#### 2.解题思路 ####

直接套快排模板：

void quick_sort(int q[], int l, int r)
    {
        
        if (l >= r) return;
    
        int i = l - 1, j = r + 1, x = q[l + r >> 1];
        while (i < j)
        {
        
            do i ++ ; while (q[i] < x);
            do j -- ; while (q[j] > x);
            if (i < j) swap(q[i], q[j]);
        }
        quick_sort(q, l, j), quick_sort(q, j + 1, r);
    }

#### 3.代码 ####

class Solution {
        
        public:
        int quickSort(vector<int>& nums,int l,int r,int k){
        
            if(l>=r) return nums[k];
            int x=nums[l+r>>1],i=l-1,j=r+1;
            while(i<j){
        
                do i++; while(nums[i]>x);
                do j--; while(nums[j]<x);
                if(i<j) swap(nums[i],nums[j]);
            }
            if(k<=j) return quickSort(nums,l,j,k);
            else return quickSort(nums,j+1,r,k);
        }
        int findKthLargest(vector<int>& nums, int k) {
        
            return quickSort(nums,0,nums.size()-1,k-1);
        }
    };

### 347. 前 K 个高频元素 ###

#### 1.题目描述 ####

> 原题链接：[347. 前 K 个高频元素][347. _ K]

![image-20220203093219688][]

#### 2.解题思路 ####

算法：`哈希表+计数排序`

具体实现：

1.  首先使用哈希表统计所有数出现的次数
2.  用计数排序，统计出出现次数最多的前k个元素的下界
3.  最后遍历哈希表，将出现次数大于下界的数加入答案

#### 3.代码 ####

class Solution {
        
    public:
        vector<int> topKFrequent(vector<int>& nums, int k) {
        
            int n=nums.size();
            map<int,int> hash;
            for(auto x:nums) hash[x]++;
            vector<int> s(n+1);
            for(auto [a,b]:hash) s[b]++;
            int i=n,t=0;
            while(t<k) t+=s[i--];
            vector<int> res;
            for(auto [a,b]:hash){
        
                if(b>i) res.push_back(a);
            }
            return res;
        }
    };

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]

[215. _K]: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
[image-20220203093144515]: https://img-blog.csdnimg.cn/img_convert/6bba6d2e6d5640f8f2c9b8ef1bdbc1fb.png
[347. _ K]: https://leetcode-cn.com/problems/top-k-frequent-elements/
[image-20220203093219688]: https://img-blog.csdnimg.cn/img_convert/6729eb5d1baea30980ab1aff9caac805.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBATEwuTEVCUk9O_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6094fd55967a4a8ca1b02a2e5dcbb6ed.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBATEwuTEVCUk9O,size_20,color_FFFFFF,t_70,g_se,x_16