72. O（N）复杂度实现找第K大的数

1.题目描述

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

2.思路及模拟

3.代码

class Solution { public: int findKthLargest(vector<int>& nums, int k) { return quickSelect(nums,k); } private: int quickSelect(vector<int>& nums, int k){ int pivot = nums[rand()%nums.size()]; vector<int> big,equal,small; for(int i = 0;i<=nums.size()-1;i++){ if(nums[i]>pivot) big.push_back(nums[i]); else if(nums[i] < pivot) small.push_back(nums[i]); else equal.push_back(nums[i]); } //k大的元素在big中 继续递归 if(k <= big.size()) return quickSelect(big,k); //k大元素在small中 if(nums.size()-small.size()<k) return quickSelect(small,k-nums.size()+small.size()); //在equal中 直接返回 return pivot; } };