215.kth-largest-element-in-an-array.java

/*
 * @lc app=leetcode id=215 lang=java
 *
 * [215] Kth Largest Element in an Array
 *
 * https://leetcode.com/problems/kth-largest-element-in-an-array/description/
 *
 * algorithms
 * Medium (48.08%)
 * Likes:    2152
 * Dislikes: 179
 * Total Accepted:    394.9K
 * Total Submissions: 813.5K
 * Testcase Example:  '[3,2,1,5,6,4]\n2'
 *
 * Find the kth largest element in an unsorted array. Note that it is the kth
 * largest element in the sorted order, not the kth 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
 * 
 * Note: 
 * You may assume k is always valid, 1 ≤ k ≤ array's length.
 * 
 */
class Solution {

    public int findKthLargest(int[] nums, int k) {
        int kth = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while (lo < hi) {
            int pivot = partition(nums, lo, hi);
            if (pivot < kth) {
                lo = pivot + 1;
            }
            if (pivot > kth) {
                hi = pivot - 1;
            }
            if (pivot == kth) {
                return nums[pivot];
            }
        }
        return nums[kth];
    }

    public int partition(int[] nums, int lo, int hi) {
        int i = lo, j = hi + 1;
        int v = nums[lo];
        while (true) {
            while (nums[++i] < v) {
                if (i == hi) {
                    break;
                }
            }
            while (nums[--j] > v) {
                if (j == lo) {
                    break;
                }
            }
            if (i >= j) {
                break;
            }
            exch(nums, i, j);
        }
        exch(nums, lo, j);
        return j;
    }

    public void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

// Quick select solution. Time complexity O(N) in average, O(N^2) in worst case