题目描述

给定整数数组 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

解答

分析

使用快排的 partition 方法，每次使用后得到枢轴pivot的最终位置

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 利用快排中的 partition 优化int len = nums.size();int left = 0, right =  len - 1;// 第k大元素下标,就是快排后第len - k 位置的元素int target = len - k;while(true){int index = partition(nums, left, right);if(index == target){return nums[index];}else if(index < target){left = index + 1;}else {right = index - 1;}}}int partition(vector<int>& nums, int left, int right){int pivot = nums[left];int j = left;// 同向移动的双指针快排// i是右指针for(int i = left + 1; i <= right; ++i){// nums[i]不满足 小于pivot的条件时，i移动到满足条件的位置时再进行和nums[j]交换if(nums[i] < pivot){j++; // 左指针右移swap(nums, j, i);}}swap(nums, j, left);return j;}void swap(vector<int>& nums, int i, int j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
};