day57—快速（选择/排序）—数组中的第 K 个最大元素（LeetCode-215）

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

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

示例 2:

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

提示：

• 1 <= k <= nums.length <= 105
• -104 <= nums[i] <= 104

解决方案：

1、lambda 表达式+暴力搜索

2、快速排序：目的是寻找下标（len-k）和对应下标的值

（一）函数源码：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {sort(nums.begin(),nums.end(),[](int &a,int &b){return a>b;});return nums[k-1];}
};

（二）函数源码：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {int left=0,right=nums.size()-1,target=nums.size()-k;int mid;while(left<right){mid=quickSelection(nums,left,right);//寻找下标if(mid==target)     return nums[mid];if(mid<target)      left=mid+1;else                right=mid-1;}return nums[left];}//x：排布值//right_max：最大右区间int quickSelection(vector<int>&nums,int x,int right_max){int i = x;//对 left 进行排布，区间从 left+1 开始int j = right_max;int ans=nums[x];while(1){ //左区间寻找下标while(i<right_max && nums[i]<=ans){i++;}//右区间while(x<j && nums[j]>ans){j--;}if(i>=j)    break;//选择完成，终止循环swap(nums[i],nums[j]);}swap(nums[x],nums[j]);return j;}
};