题解 | #寻找第K大#
寻找第K大
https://www.nowcoder.com/practice/e016ad9b7f0b45048c58a9f27ba618bf
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param a int整型一维数组 * @param n int整型 * @param K int整型 * @return int整型 */ public int findKth (int[] a, int n, int K) { // write code here quickSort(a,0,n-1); return a[n-K]; } public void quickSort(int[] a,int left,int right){ if(left>=right){ return; } int p=partition(a,left,right); quickSort(a,left,p-1); quickSort(a,p+1,right); } public int partition(int[] a,int left,int right){ int pv=a[right];//基准点 int i=left; int j=left; while(j<right){ if(a[j]<pv){ //找到比基准点更小的了 if(i!=j){ swap(a,i,j); } i++; } j++; } swap(a,i,right); return i; } public void swap(int[] a,int i,int j){ int temp=a[i]; a[i]=a[j]; a[j]=temp; } }