题解 | #寻找第K大# [S-P0]

import java.util.*;

public class Solution {
    int M;
    int[] aa;
    public int findKth(int[] a, int n, int K) {
      M = n - K;
      aa = a;
      quickSortM(0, n-1);
      return aa[M];
    }

    private void quickSortM(int start, int end) {
      if (start >= end) return;
      
      int pivot = partition(start, end);
      if (pivot == M) return;
      if (pivot < M) quickSortM(pivot+1, end);
      else quickSortM(start, pivot-1);
    }
  
    private int partition(int start, int end) {
      int pVal = aa[start];
      int x = start, y = end;
      while (x < y) {
        while (aa[x] <= pVal && x < end) x++;
        while (aa[y] >= pVal && y > start) y--;
        if (x < y) swap(x, y);
      }
      swap(start, y);
      return y;
    }
  
    private void swap(int x, int y) {
      int tmp = aa[x];
      aa[x] = aa[y];
      aa[y] = tmp;
    }
}