题解 | #寻找第K大#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型一维数组 
     * @param n int整型 
     * @param K int整型 
     * @return int整型
     */
    List<int> a;
    public int findKth (List<int> a, int n, int K) {
        this.a = a;
        int left = 0;
        int right = n - 1;
        int res = Partition(left, right);
        while(res != n - K){
            res = Partition(left, right);
            if(res > n - K) right = res;
            else left = res;
        }
        return a[n - K];
    }
    public int Partition(int left, int right){
        Random ran = new Random();
        int dom = ran.Next(left, right + 1);
        int pivot = a[dom];
        int start = left;
        Swap(dom, left++);
        while(left <= right){
            if(a[right] < pivot && a[left] > pivot) Swap(left++, right--);
            if(a[right] >= pivot) right--;
            if(a[left] <= pivot) left++;
        }
        
        Swap(start,right);
        return right;
    }
    public void Swap(int x, int y){
        int cur = a[x];
        a[x] = a[y];
        a[y] = cur;
    }
}