k最大的三种题解

一、排序出答案

空间复杂度（1）时间复杂度（nlogn）

import java.util.*;
public class Solution {
    
    public int findKth(int[] a, int n, int K) {
        // write code here
        Arrays.sort(a);
        return a[n-K];
        
    }
}

二、优先队列

空间复杂度（n）时间复杂度（nlogn）

import java.util.*;

public class Solution {
  
    public int findKth(int[] a, int n, int K) {
       PriorityQueue<Integer> que = new PriorityQueue<>();
		for(int i = 0; i < n;i++) {
			if(que.size()<K) {
				que.add(a[i]);
			}else if(a[i]>que.peek()) {
				que.remove();
				que.add(a[i]);
			}
		}	
		return que.peek();
    }
}

三、快速排序

空间复杂度（1） 时间复杂度（nlogn）

import java.util.*;

public class Solution {
    
    public void findKth(int[] a, int l, int r,int K){
        if(l>=r)return;
        int top = a[l];
        int i,j;
        
        i = l;j = r;
        while(i<j){
            while(i<j&&a[j]>top)j--;
            if(i<j)a[i++]=a[j];
            while(i<j&&a[i]<top)i++;
            if(i<j)a[j--]=a[i];
        }
        if(i==j)a[i] = top;
        if(i==K)return;
        else if(i<K)findKth(a,i+1,r,K);
        else findKth(a,l,i,K);
    }
    
    public int findKth(int[] a, int n, int K) {
      findKth(a, 0, n-1, n-K);
      return a[n-K];
    }
}