LeetCode 215. Kth Largest Element in an Array [Medium]

题目来源：https://leetcode.com/problems/kth-largest-element-in-an-array/

题目难度：Medium

解答1[Java]：

import java.util.Arrays;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums[len-k];
    }
}

但是这个实现依赖了 Java 的库，并不是一个通用的解法。

解答2

//move the k largest elements to the left part of array
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums.length == 1)
            return nums[0];

        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int pivotPos = partition(nums, left, right);
            if (pivotPos - left + 1 < k) {
                k = k - (pivotPos - left + 1);// shrink k value
                left = pivotPos + 1;// move left to pivotPos + 1
            } else if (pivotPos - left + 1 > k) {
                right = pivotPos - 1;// shrink right by 1 at least
            } else {
                return nums[pivotPos];
            }
        }
        return 0;
    }

    // make elements value between [0, leftBound] are all >= pivot
    private int partition(int[] array, int left, int right) {
        int pivotIndex = left + (right - left) / 2;
        int pivot = array[pivotIndex];
        swap(array, pivotIndex, right);

        int leftBound = left;
        int rightBound = right - 1;
        while (leftBound <= rightBound) {
            if (array[leftBound] >= pivot) {
                leftBound++;
            } else if (array[rightBound] < pivot) {
                rightBound--;
            } else {
                swap(array, leftBound++, rightBound--);
            }
        }
        swap(array, leftBound, right);
        return leftBound;
    }

    private void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

要理解这个算法需要对快速排序算法有所了解。

每次 partition 之后，pivotPos 左边的元素都是大于 pivotPos的，右边的都是小于 PivotPos的，根据 pivotPos的index 和 k 的关系就能确定如果要继续寻找是在 pivotPos 左边寻找还是右边寻找。

参考资料

1. 深入理解Java PriorityQueue