求无序数组中第k大的数，如果我们先将数组排序，然后再得到第k大的数，就前面所学的排序算法而言，最好的时间复杂度也是O（n*logn）。我们可以借助快速排序的划分方法，实现一个时间复杂度为O（n）的解法。
public static void partition(int[] arr,int l,int r,int x){
first=l;
last=r;
int i=l;
while(i<=last){
if(arr[i]<x){
swap(arr,i,first);
i++;
first++;
}
else if(arr[i]==x) i++;
else {
swap(arr,i,last);
last--;
}
}
}
划分图解
class Solution {
public int findKthLargest(int[] nums, int k) {
// 由于是升序排序，求第k大的数就是求第n-k小的数
return selectNum(nums,nums.length-k);
}
public static int first,last;
public static void swap(int[] arr,int i,int j){
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
public static int selectNum(int[] arr,int i){
int ans=-1;
for(int l=0,r=arr.length-1;l<=r;){
partition(arr,l,r,arr[l+(int)(Math.random()*(r-l+1))]);
if(i<first) r=first-1;
else if(i>last) l=last+1;
else {
ans=arr[i];
break;
}
}
return ans;
}
public static void partition(int[] arr,int l,int r,int x){
first=l;
last=r;
int i=l;
while(i<=last){
if(arr[i]<x){
swap(arr,i,first);
i++;
first++;
}
else if(arr[i]==x) i++;
else {
swap(arr,i,last);
last--;
}
}
}
}
时间复杂度分析
最好和最差情况时间复杂度
由于我们这里选择了从数组中随机选择数的方法，因此根据期望，时间复杂度可达O（n）。
