题解 | #寻找第K大#TOP47

思路:
1.快速排序的三路法
2.使得区间内 [left, lt) > value, [lt, gt) == value, [gt, right] < value
3.如果k-1 在 [lt, gt)之间，那就找到了第K大的数
4.主要是注意排序的规则

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if(a == null ||a.length < 1){
            return -1;
        }
        int left = 0;
        int right = a.length - 1;
    
        return part(a, left, right, K-1);
    }
    private int part(int[] data, int left, int right, int K){
        int index = new Random().nextInt(right - left +1);
        int value = data[index+left];
        data[index+left] = data[left];
        data[left] = value;
        
        int lt = left;
        int gt = right + 1;
        int i = left + 1;
        
        while(i < gt){
            if(data[i] < value){
                int temp = data[gt-1];
                data[gt-1] = data[i];
                data[i] = temp;
                gt --;
            }else if(data[i] > value){
                int temp = data[lt];
                data[lt] = data[i];
                data[i] = temp;
                i++;
                lt++;
            }else{
                i++;
            }
        }
        
        if(lt <= K && K < gt){
            return data[K];
        }
        
        if(lt > K){
            //左边
            return part(data, left, lt -1, K);
        }else{
            return part(data, gt , right, K);
        }
    }
}