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


给定整数数组 nums 和整数 k,请返回数组中第 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
 

提示:

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


维护k个长度的 小顶堆,堆顶为要求的值(topK用小顶堆)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 使用数组构建小顶堆
        int[] top = new int[k];
        // 将 nums 数组中的前 k 个元素取出来
        for (int i = 0; i < k; i++) {
            top[i] = nums[i];
        }
        // 先建堆,然后依次比较剩余元素与堆顶元素的大小,比堆顶大的,说明它应该在堆中出现,则用它来替换掉堆顶元素,然后沉降。
        buildHeap(top);
        for (int j = k; j < nums.length; j++) {
            int temp = top[0];
            if (temp < nums[j]) {
                setTop(top, nums[j]);
            }
        }
        return top[0];
    }

    private void setTop(int[] nums, int num) {
        nums[0] = num;
        heapify(nums, 0, nums.length);
    }

    private void buildHeap(int[] top) {
        //找到第一个非叶子节点,遍历调整
        int startHeapify = (top.length - 1) / 2;
        for (int i = startHeapify; i >= 0; i--) {
            heapify(top, i, top.length);
        }
    }
    public void heapify(int[] nums, int index, int length) {
        //左孩子,右孩子
        int left = (index << 1) + 1;
        int right = (index << 1) + 2;
        int min = index;
        //找到3个中最小的 (根左右)
        if (left < length && nums[left] < nums[min]) {
            min = left;
        }
        if (right < length && nums[right] < nums[min]) {
            min = right;
        }
        //如果当前不是3个中最小的 交换位置后 递归
        if (min != index) {
            swap(nums, min, index);
            heapify(nums, min, length);
        }
    }

    private void swap(int[] nums, int min, int index) {
        int a = nums[min];
        nums[min] = nums[index];
        nums[index] = a;
    }
}

查看原文

  • 作者:低调做个路人 (扫码联系作者)
  • 发表时间:2021-10-01 21:34:30
  • 版权声明:自由转载-非商用-非衍生-保持署名(创意共享3.0许可证)
  • 评论