题解 | 寻找第K大 （符合题目空间复杂度o(1)要求）

import java.util.*;


public class Solution {
    private int first = 0;
    private int last = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param n int整型
     * @param K int整型
     * @return int整型
     */
    public int findKth (int[] a, int n, int K) {
        // write code here
        int targetIndex = n - K; // 计算目标位置
        int l = 0;
        int r = n - 1;
        while (r >= l) {
            partion(a, l, r);
		  // 分区后可以等于pivot值的区域已经排好序了，如果目标位置位于这段区域，则返回
            if (targetIndex >= first && targetIndex <= last) {
                return a[targetIndex];
            } else if (targetIndex < first) {
                r = first  - 1;
            } else {
                l = last + 1;
            }
        }
        return -1;
    }

	// 使用的是左神荷兰国旗优化后的分区方式，将数组划分为小于pivot,等于pivot以及大于pivot的三份
    private void partion(int[] a, int l, int r) {
        int randomPrivotIndex = l + ((int) Math.random() * (r - l + 1));
        int pivot = a[randomPrivotIndex];
        System.out.println(pivot);
        first = l;
        last = r;
        int i = l;
        while (i <= last) {
            if (a[i] < pivot) {
                swap(a, first, i);
                first++;
                i++;
            } else if (a[i] == pivot) {
                i++;
            } else {
                swap(a, last, i);
                last--;
            }
        }
    }

    public void swap(int[] num, int i, int j) {
        int t = num[i];
        num[i] = num[j];
        num[j] = t;
    }
}