215. Kth Largest Element in an Array

JIAKAOBO

LeetCode

感谢赞助!

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