• ㊗️
• 大家
• 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 {
public int findKthLargest(int[] nums, int k) {
int left = 0;
int right = nums.length - 1;

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

}

private int findPosition(int[] nums, int left, int right){
// 把nums[left]这个数当作pivot
int curr = nums[left];

int l = left + 1;
int r = right;
// 使得 curr 左边的值都大于它, curr右边的值都小于它
// 要使用 <=, 否则[2,1] 1 这种情况会报错
while(l <= r){
if(nums[l] < curr && nums[r] > curr){
swap(nums, l, r);
l++;
r--;
}
// 跳过符合条件的值
if(nums[l] >= curr) l++;
if(nums[r] <= curr) r--;
}

// 把curr放到对的位置
// r指向第一个比curr大的数, 所以要让curr和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.