• ㊗️
• 大家
• offer
• 多多！

## Problem

Find the $k^{th}$ largest element in an unsorted array. Note that it is the $k^{th}$ largest element in the sorted order, not the $k^{th}$ distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Constraints:

• $1 <= k <= nums.length <= 10^5$
• $-10^4 <= nums[i] <= 10^4$

## Code

703. Kth Largest Element in a Stream

Quickselect: find the kth smallest/largest element in an unordered list

class Solution {
// part of quick sort
public int findKthLargest(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;

while (left <= right) {
// pos + 1 就是第几大数
int pos = findPosition(nums, left, right);
if (pos == k - 1) {
return nums[pos];
} else if (pos > k - 1) { // 选定的数字小了, 结果在 pos 左边
right = pos - 1;
} else {
left = pos + 1; // 选定的数字大了, 结果在 pos 右边
}
}

return -1;
}

private int findPosition(int[] nums, int left, int right) {
int pivot = nums[left];

int l = left + 1;
// 指向第一个大于curr的数字, 所以最后和r进行交换
int r = right;
// 使 curr 左边的值都大于它, 右边的值都小于它
// 要使用 <=
// 否则[2,1] 1 这种情况会报错
while (l <= r) {
if (nums[l] < pivot && nums[r] > pivot) {
swap(nums, l, r);
l++;
r--;
}
// 跳过符合条件的值
if (nums[l] >= pivot)
l++;
if (nums[r] <= pivot)
r--;
}

swap(nums, left, r);
return r;
}

private void swap(int[] nums, int left, int right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
}
}

Time complexity: $O(N)$ in the average case, $O(N^2)$ in the worst case.