【常见面试算法】数组中第k大的数

给定一个数组A，要求找到数组A中第K大的数字。对于这个问题，解决方案有不少，此处我只给出三种：

方法1：

对数组A进行排序，然后遍历一遍就可以找到第K大的数字。该方法的时间复杂度为O(N*logN)

方法2：

利用简单选择排序法的思想，每次通过比较选出最大的数字来，比较上K次就能找出第K大的数字来。该方法的时间复杂度为O(N*K)，最坏情况下为O(N^2)。

方法3：

class Solution {
    
    static int kk; // 第k大元素的快排后索引位置；
    
    public int findKthLargest(int[] nums, int k) {
        kk = nums.length - k; 
        quickSort(nums, 0, nums.length-1);     
        return nums[kk];
    }
    
    private void quickSort(int[] data, int start, int end){
        if(start < end){
            int mid = partition(data, start,end);
            //当第k大位置的数字归位时，结束递归遍历；
            if(mid == kk) return;
            else if(mid > kk) quickSort(data, start, mid-1); 
            else quickSort(data, mid+1, end);
            
        }
    }
    
    private int partition(int[] data, int start, int end ){
        int key = data[start];
        if(start > end) return -1;
        while(start < end){
            //一定要从后往前遍历！
            while(start < end && data[end] >= key) end--;
            if(start < end) swap(data, start, end);
            while(start < end && data[start] <= key) start++;
            if(start < end) swap(data, start, end);            
        }
        
        return start;
    }
    
    private void swap(int[] data, int i, int j){
        int tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
}