Kth Largest Element in an Array

1package pkg5leetcode.top100;2 3/*4 * Kth Largest Element in an Array | LC 2155 * APPROACH: Quickselect partition around pivot target index.6 * COMPLEXITY: Time O(n) average, Space O(1)7 */8public class top100_LC215KthLargestElementInAnArray {9    static int findKthLargest(int[] nums, int k) {10        int target = nums.length - k;11        int lo = 0, hi = nums.length - 1;12        while (true) {13            int p = partition(nums, lo, hi);14            if (p == target) return nums[p];15            if (p < target) lo = p + 1;16            else hi = p - 1;17        }18    }19 20    static int partition(int[] a, int lo, int hi) {21        int pivot = a[hi], i = lo;22        for (int j = lo; j < hi; j++) {23            if (a[j] <= pivot) swap(a, i++, j);24        }25        swap(a, i, hi);26        return i;27    }28 29    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }30 31    public static void main(String[] args) {32        check(findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2) == 5, "case1");33        check(findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4) == 4, "case2");34        System.out.println("all tests passed");35    }36 37    static void check(boolean cond, String name) {38        if (!cond) throw new AssertionError("FAILED: " + name);39        System.out.println("  PASS " + name);40    }41}