【LeetCode】215. Kth Largest Element in an Array (Medium)

【题意】找出第k大的元素

【解】类似快排

class Solution { public: int findKthLargest(vector<int>& nums, int k) { return f(nums, 0, nums.size(), k); } private: int f(vector<int>& nums, int l, int r, int k) { int pivot = nums[l]; int i = l + 1; for (int j = i; j < r; j++) { if ((nums[j] < pivot)) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; i++; } } nums[l] = nums[i - 1]; nums[i - 1] = pivot; if (l >= r) return nums[l]; if (i - l + k == r - l + 1) return nums[i - 1]; else if (i - l + k > r - l + 1) return f(nums, l, i - 1, k - r + i - 1); else return f(nums, i, r, k); } };