2023/10/11 LeetCode

LeetCode P215数组中第K个最大元素
描述： 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

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

/**
     * P215数组中第k个最大元素(堆排序的做法)
     * @param nums
     * @param k
     * @return
     * 思路：堆排序只需要从堆顶取k-1个元素即是第k个最大元素值
     */
    public int findKthLargest(int[] nums, int k) {
        //构建堆，从最后一个没有叶子结点的开始
        for (int i=nums.length/2-1;i>=0;i--) {
            maxHeapify(nums,nums.length,i);
        }
        System.out.println(Arrays.toString(nums));
        for (int i=nums.length-1; i >= nums.length - k + 1;i--) {
            swap(nums,0,i); //将最大值放入数组最后
            maxHeapify(nums,i,0); //删除最后一个节点重建堆

        }
        return nums[0];
    }

    /**
     *
     * @param nums 数组
     * @param n 数组个数
     * @param i 当前堆顶元素下标
     */
    public void maxHeapify(int[] nums,int n,int i) {
        int largeMax = i;
        int left = i*2+1;
        int right = i*2+2;
        if (left<n&&nums[left]>nums[largeMax]) {
            largeMax = left;
        }
        if (right<n&&nums[right]>nums[largeMax]) {
            largeMax = right;
        }
        if (largeMax!=i) {
            swap(nums,i,largeMax); //将最大值放入堆顶
            maxHeapify(nums,n,largeMax); //重建堆
        }
    }

    /**
     * 数组交换
     * @param num
     * @param l
     * @param r
     */
    public void swap(int[] num,int l,int r) {
        int temp = num[l];
        num[l] = num[r];
        num[r] = temp;
    }