0215. Kth Largest Element in an Array

https://leetcode.com/problems/kth-largest-element-in-an-array

Description

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= k <= nums.length <= 104

• -104 <= nums[i] <= 104

ac1: quick select

Iterative version:

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Edge cases: invalid input.

        k--; // Kth largest, index = k - 1 in sorted array.
        int start = 0, end = nums.length - 1;
        while (start <= end) {
            int p = getArrayPartitionIndex(nums, start, end);
            if (p == k) return nums[p];

            if (p < k) {
                start = p + 1;
            } else if (p > k) {
                end = p - 1;
            }
        }

        return -1;
    }

    private int getArrayPartitionIndex(int[] nums, int start, int end) {
        int pivot = nums[end];
        int left = start;
        for (int right = start; right < end; right++) {
            if (nums[right] >= pivot) {
                swap(nums, left, right);
                left++;
            }
        }
        swap(nums, left, end);
        return left;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Recursive versioned:

// quick select: set pivot, opposite direction two pointers

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // sort, nlogn
        // partition, quick select
        // pivot, left/right

        // edge cases
        if (nums.length < 1) return -1;

        return quickSelect(nums, 0, nums.length-1, k);
    }
    private int quickSelect(int[] nums, int s, int e, int k) {
        // exit
        if (s == e) return nums[s];

        // init
        int l = s, r = e, pivot = nums[(s+e)/2];

        // loop
        while (l <= r) {
            while(l<=r && nums[l] > pivot) l++; // cannot put '==' here, will pass then entire list, cause stackoverfloww
            while (l <= r && nums[r] < pivot) r--;
            if (l <= r) {
                if (l < r) swap(nums, l, r);
                l++;
                r--;
            }
        }

        // determine which part contains kth
        if (s + k - 1 <= r) return quickSelect(nums, s, r, k);
        if (s + k - 1 >= l) return quickSelect(nums, l, e, k-(l-s)); //  be careful set new value for k by k-(l-s)
        return nums[r+1]; // when there is value in the middle, right, kth, left
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

// Time: O(n)

ac2: priority queue

O(NlogK)