写点什么

【LeetCode】数组中的第 K 个最大元素 Java 题解

作者:HQ数字卡
  • 2022 年 5 月 20 日
  • 本文字数:832 字

    阅读完需:约 3 分钟

题目描述

给定整数数组 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
来源:力扣(LeetCode)链接:https://leetcode.cn/problems/kth-largest-element-in-an-array著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的算法题目是数组排序题目,求的是数组中第 k 个最大的元素。

  • 我们首先可以对数组整体排序,数组中第 n - k 个位置的元素即为答案。

  • 我们也可以使用堆数据结构实现这个算法。维护一个占用空间为 k 的优先队列。如果当前堆不满,直接添加。当堆长度为 k 的时候,则需要动态更新堆顶元素。占用的空间较小。实现代码如下,供参考。

通过代码

  • 系统函数算法


class Solution {    public int findKthLargest(int[] nums, int k) {        int n = nums.length;        Arrays.sort(nums);        return nums[n - k];    }}
复制代码


  • 堆解法


class Solution {    public int findKthLargest(int[] nums, int k) {        int ans = 0;        if (nums.length == 0) {            return ans;        }        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k);        for (int num : nums) {            if (priorityQueue.size() < k) {                priorityQueue.add(num);            } else {                if (priorityQueue.peek() < num) {                    priorityQueue.poll();                    priorityQueue.add(num);                }            }        }
ans = priorityQueue.poll(); return ans; }}
复制代码

总结

  • 系统函数排序,也就是快速排序的解法的时间复杂度是 O(n log n), 空间复杂度是 O(log n)

  • 优先队列解法的时间复杂度是 O(n), 空间复杂度是 O(n)

  • 坚持算法每日一题,加油!

发布于: 刚刚阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】数组中的第K个最大元素Java题解_LeetCode_HQ数字卡_InfoQ写作社区