数组中的第K个最大元素-蒲公英云

数组中的第K个最大元素

灰太狼 2023-07-14 12:58 70阅读 0赞

题目：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1：

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

示例2：

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

说明：
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路：
这个是个典型的 Top K 问题，而且题目里面没有说明数据量的大小或限定的内存，那么直接用堆排序秒了就行。
思路是创建一个小顶堆，将所有数组中的元素加入堆中，并保持堆的大小小于等于 k。这样，堆中就保留了前 k 个最大的元素。这样，堆顶的元素就是正确答案。
向大小为 k 的堆中添加元素的时间复杂度为 O(log k)，我们将重复该操作 N 次，故总时间复杂度为 O(N*log k)
贴出笔者的代码：

class Solution { 
    //返回第K个最大的元素
    public int findKthLargest(int[] nums, int k) { 
        //创建一个堆
        int[] haep = new int[k];
        for(int i=0; i<k; i++) { 
            haep[i] = nums[i];
        }
        //把堆调整为小顶堆
        for(int i = haep.length / 2 - 1; i >=0; i--) { 
            adjustHeap(haep, i, k);
        }
        //循环遍历，对每个元素进行调整
        for(int i=k; i<nums.length; i++) { 
            if(nums[i] > haep[0]) { 
                haep[0] = nums[i];
                adjustHeap(haep, 0, k);
            }
        }
        return haep[0];
    }
    //单次调整
    public  static void adjustHeap(int arr[], int i, int lenght) { 
        int temp = arr[i];//先取出当前元素的值，保存在临时变量
        //开始调整
        //说明
        //1. k = i * 2 + 1 k 是 i结点的左子结点
        for(int k = i * 2 + 1; k < lenght; k = k * 2 + 1) { 
            if(k+1 < lenght && arr[k] > arr[k+1]) {  //说明左子结点的值小于右子结点的值
                k++; // k 指向右子结点
            }
            if(arr[k] < temp) {  //如果子结点大于父结点
                arr[i] = arr[k]; //把较大的值赋给当前结点
                i = k; //!!! i 指向 k,继续循环比较
            } else { 
                break;//!
            }
        }
        //当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
        arr[i] = temp;//将temp值放到调整后的位置
    }
}