題目介紹

題解

法一：基于快速排序的選擇方法

以中間元素pivot為基準進行排序后，右指針 r 的位置就是最終全部排序好后pivot的位置，然后去左邊或右邊遞歸尋找第k個位置（答案）的元素。

代碼如下：

class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;return quickselect(nums, 0, n - 1, n - k);}// 返回最終排序后數組第k個位置的元素public int quickselect(int[] nums, int left, int right, int k) {if (left == right) { // 區間只剩一個元素，直接返回  >=也可以return nums[k];}int mid = left + (right - left) / 2;int pivot = nums[mid];int l = left, r = right;while (l <= r) {！！！不能用<=，是為了防止中軸值（pivot）被多次交換while (nums[l] < pivot)l++; while (nums[r] > pivot)r--; if (l <= r) {swap(nums, l, r); l++;r--;}}// 遞歸處理左半部分或右半部分if (k <= r) {return quickselect(nums, left, r, k); // 目標在左半部分} else {return quickselect(nums, l, right, k); // 目標在右半部分}}public void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}