JIAKAOBO

LeetCode

venmo
wechat

感谢赞助!

  • ㊗️
  • 大家
  • 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.