题解 | #寻找第K大#

记录

import java.util.*;

public class Solution {
    Random random = new Random();
    public int findKth(int[] a, int n, int K) {
        // write code here
        int l = 0;
        int r = n - 1;
        int target = n - K;
        while (true){
            int index = partition(a, l, r);
            if (index == target){
                return a[index];
            } else if (index < target){
                l = index + 1;
            } else {
                r = index - 1;
            }
        }
    }
    public int partition(int[] a, int l, int r){
        if (r > l){
            int index = l + 1 + random.nextInt(r - l);
            swap(a, l ,index);

        }
        int privot = a[l];
        int j = l;
        for (int i = l + 1; i <= r; i++){
            if (a[i] < privot){
                j++;//为了中间出现大于privot，后面有小于的来的，j可以指向大于的，这样就交换
                swap(a, j, i);
            }
        }
        swap(a, j, l);//l还是为参考的值，j现在是最后一个小于参考值的数
        return j;
    }
    public void swap(int[] a, int i, int j){
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }


}