215.数组中的第k个最大元素

LeetCode 算法题解与代码实现

class Solution {
    private static final Random rand = new Random();

    public int findKthLargest(int[] nums, int k) {
        return partition(nums, 0, nums.length-1, k);
    }

    // [left, right]
    // 循环不变量:
    // pivot | > pivot | i .... j | < pivot
    private int partition(int[] nums, int left, int right, int k) {
        swap(nums, left, left+rand.nextInt(right - left + 1));
        int pivot = nums[left], i = left+1, j = right;
        while (true) {
            // i 会停留在第一个 >= pivot的位置上
            while (i <= j && nums[i] > pivot)
                i++;
            // j 会停留在第一个 <= pivot的位置上
            while (i <= j && nums[j] < pivot)
                j--;
            if (i >= j)
                break;
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, left, j);
        if (j == k-1) return nums[k-1];
        else if (j < k) return partition(nums, j+1, right, k);
        else return partition(nums, left, j-1, k);
    }
    // 7 5 6

    private void swap(int[] nums, int l, int r) {
        int tmp = nums[l];
        nums[l] = nums[r];
        nums[r] = tmp;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums= new int[]{4,5,6,7,0,1,2};
        int k = 0;
        System.out.println(s.findKthLargest(nums, k));
    }
}