一、题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例?2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
?

提示：

1 <= k <= nums.length <= 105
-104?<= nums[i] <= 104

二、思路讲解

? ? ? ? 2.1 方法一：暴力

? ? ? ? 首先很容易想到将数组排序，然后找到第k大的数字。

public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }

? ? ? ? 时间复杂度：? ? ? ? O(NlogN)

? ? ? ? 空间复杂度：? ? ? ? O(1)?

? ? ? ? 虽然可以通过，但是快速排序的时间复杂度达到了NlogN。我们还需要降低时间复杂度。

? ? ? ? 2.2 方法二：快速选择?

? ? ? ? 根据快速排序的知识我们可以知道，每次partition算法会将所选的基准数（记为target）放到正确的位置，而我们其实只需要知道第k大的位置上的数是什么，而不需要关心其他位置是否有序。那么我们可以根据基准数的位置来判断，假如k在target的左边，那么我们只需要递归target左边即可，而不需要关心target右边是否有序；反之，如果k在target右边，我们只需要递归右边。

class Solution {
    
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length-1, nums.length-k);
    }

    /**
        partition算法
     */
    int partition(int []nums, int i, int j) {
        int target = nums[i];
        while(i<j) {
            while(i<j && nums[j]>=target) {
                j--;
            }
            nums[i] = nums[j];
            while(i<j && nums[i]<=target) {
                i++;
            }
            nums[j] = nums[i];
        }
        nums[i] = target;
        return i;
    }

    /**
        快速选择算法
     */
    int quickSelect(int []nums, int i, int j, int index) {
        if(i>=j) {
            return nums[i];
        }
        int k = partition(nums, i, j);
        if(k == index) {
            return nums[k];
        } else if(k < index) {
            //只递归右半边
            return quickSelect(nums, k+1, j, index);
        } else {
            //只递归左半边
            return quickSelect(nums, i, k-1, index);
        }
    }
}

? ? ? ? 时间复杂度：? ? ? ? O(N)

? ? ? ? 空间复杂度：? ? ? ? O(logN)????????递归使用栈空间的空间代价的期望为 O(logn)?

? ? ? ? 2.3 方法三：堆排序?

? ? ? ? 了解堆排序的朋友们应该可以想到，构建一次大顶堆，堆顶元素就是数组中最大的数，构建第二次大顶堆，堆顶元素就是第二大的数……那么，我们构建k次大顶堆，堆顶元素就是第k大的数了。

class Solution {
    
    public int findKthLargest(int[] nums, int k) {        
        return heapSort(nums, k);
    }

    int heapSort(int []nums, int k) {
        for (int i = nums.length/2-1; i >= 0; i--) {
            adjustHeap(nums, i, nums.length);
        }

        //操作k-1次，即可找到第k大的元素
        for (int i=nums.length-1; i>nums.length-k-1; i--) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;
            adjustHeap(nums, 0, i);
        }
        return nums[nums.length-k];
    }

    void adjustHeap(int []nums, int i, int length) {
        int temp = nums[i];
        for (int k=2*i+1; k<length; k=2*k+1) {
            if ((k+1)<length && nums[k]<nums[k+1]) {
                k++;
            }
            if (nums[k]>temp) { 
                nums[i] = nums[k];   
                i = k;  
            } else {
                break;  
            }
        }
        nums[i] = temp;
    }
}

? ? ? ? 2.4 方法四：计数排序

? ? ? ? 题目中只要求时间，没有要求空间，且数字的范围不算很大，那就很适合计数排序了。思想很简单，就不过多介绍了。

class Solution {
    
    public int findKthLargest(int[] nums, int k) {
        
        //考虑负数
        int []count = new int[20001];
        for(int num : nums) {
            count[num+10000]++;
        }
        
        for(int i=count.length-1; i>=0; i--) {
            k -= count[i];
            if(k<=0) {
                return i-10000;
            }
        }
        return -1;
    }
}

? ? ? ? 时间复杂度：? ? ? ? O(N)

? ? ? ? 空间复杂度：? ? ? ? O(N)