当前位置：首页 > article >正文

leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现

article 2024/11/27 20:03:23

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

题目描述

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

请注意，要求排名是从大到小的，因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。

示例 1：

输入：nums = [3,2,1,5,6,4], k = 2
输出：5
解释：数组中第二大的元素是 5。

示例 2：

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4
解释：数组中第四大的元素是 4。

Java 实现代码

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 使用最小堆来找第k大的元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // 维护堆的大小为k，去除堆中最小的元素
            }
        }

        return minHeap.peek(); // 最小堆的根就是第k大的元素
    }
}

解题思路

最小堆方法：我们可以利用最小堆（PriorityQueue）来实现。堆是一个完全二叉树，可以在 O(logn) 时间内进行插入和删除操作。

将数组中的前 k 个元素插入到最小堆中。
如果当前堆中元素个数大于k，则吐出。
最后，堆顶的元素就是第 k 大的元素。

这种方法的时间复杂度是 O(n log k)，其中 n 是数组的大小，k 是需要找到的第 k 大元素。

快速选择法：另一种方法是使用快速排序的思想，即快速选择（Quickselect）。通过对数组进行划分，选择性地进入有可能包含第 k
大元素的子数组。这个方法的平均时间复杂度是 O(n)。

复杂度分析

时间复杂度: 使用最小堆方法时，插入一个元素的时间复杂度是 O(log k)，所以对于数组中 n 个元素，总的时间复杂度是 O(n log k)。
空间复杂度: O(k)，因为堆中最多存储 k 个元素。

举例说明执行过程

假设有数组 nums = [3,2,1,5,6,4]，我们要求第 2 大的元素。

初始数组：[3,2,1,5,6,4]，k = 2
创建一个大小为 2 的最小堆：
插入 3，堆为 [3]
插入 2，堆为 [2, 3]（因为堆是最小堆，所以自动调整）
插入 1，堆为 [1, 3]（删除最小元素 2）
插入 5，堆为 [3, 5]（删除最小元素 1）
插入 6，堆为 [5, 6]（删除最小元素 3）
插入 4，堆为 [5, 6]（删除最小元素 4）

最终堆中元素为 [5, 6]，堆顶为 5，即第 2 大元素。