数组中第K大的元素

215. 数组中的第K个最大元素

给定整数数组 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

快速选择

1.随机选取一个元素作为中枢划分数组，中枢左边元素比中枢值大，中枢右边元素比中枢值小

2.如果划分后，中枢元素下标为k-1，说明中枢正好是第k大元素

3.否则，中枢元素下标<k-1，第k大元素在右半区间，右边区间重复1操作

4.中枢元素下标>k-1，第k大元素在左边区间，左边区间重复1操作

注意：使用填坑法对nums进行划分时，需要将nums[left]放到随机的pivot_index上面，因为nums[left]会最先被替换掉。

而传统的快速排序因为把nums[left]作为pivot，所以不需要这一步

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


    //快速选择，中枢左边元素大，右边元素小
    public int partition(int[] nums , int k, int left , int right){
        int pivot_index = new Random().nextInt(right-left + 1) + left;//取随机下标元素作为中枢
        //new Ramdom().nextInt(num),数据范围为[0,num)
        int pivot = nums[pivot_index]; //中枢的数值
        nums[pivot_index] = nums[left]; //移动最左元素,因为最左元素需要最先被替换
        int i = left, j = right;
        //大的元素放到左边，小的元素放到右边
        while(i < j){
            while(i < j && nums[j] <= pivot) j--;
            nums[i] = nums[j];
            while(i < j && nums[i] >= pivot) i++;
            nums[j] = nums[i];
        }
        nums[i] = pivot; //确定中枢最终位置
        
        if(i < k-1){ //第k个最大元素在右边
            return Partition(nums, k, i+1, right);
        }else if(i > k-1){ //第k个最大元素在左边
            return Partition(nums, k, left, i-1);
        }
        return nums[i];
    }      
}

时间复杂度：$O(n)$，引入随机化进行数组划分，它的时间代价的期望是 $O(n)$
空间复杂度：$O(log⁡n)$，递归使用栈空间的空间代价的期望为 $O(log⁡n）$

堆排序

建立大根堆，删除k-1次元素后，堆顶元素为第k大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        buildHeap(nums, len);
        for(int i = 0 ; i < nums.length; i++){
            System.out.println(nums[i]);
        }
        for(int i = len-1; i >= len-(k-1) ;i--){ //删除k-1次，堆顶即为第k大
            swap(nums, 0, i);
            adjustHeap(nums, 0, i);
        }
        return nums[0];
    }

    public void buildHeap(int[] nums, int len){//建立大顶堆
        for(int i = len/2-1 ; i >= 0; i--){
            adjustHeap(nums, i, len);
        }
    }

    public void adjustHeap(int[] nums, int k, int len){//从下标k调整堆
        while(2 * k + 1 < len){
            int i = 2 * k + 1; //i为k结点的左孩子
            if(i + 1 < len && nums[i] < nums[i+1]){//右孩子比左孩子大
                i++;
            }
            if(nums[k] < nums[i]){//待调整结点比孩子小，交换
                swap(nums, k, i);
                k = i; //待调整元素变为i结点
            }else{//该节点已经满足大顶堆要求
                 break;
            }
        }
    }
    
    public void swap(int[] nums, int i, int j){ //交换元素
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：$O(nlog⁡n)$，建堆的时间代价是 $O(n)$，删除k-1次，每次删除向下调账时间代价为logn，删除的总代价是 $O(klog⁡n)$，因为 k<n，故渐进时间复杂为 $O(n+klog⁡n)=O(nlog⁡n)$
空间复杂度：$O(log⁡n)$，即递归使用栈空间的空间代价