【LeetCode】数组中的第 K 个最大元素 Java 题解
题目描述
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。
请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
复制代码
思路分析
今天的算法题目是数组排序题目,求的是数组中第 k 个最大的元素。
我们首先可以对数组整体排序,数组中第 n - k 个位置的元素即为答案。
我们也可以使用堆数据结构实现这个算法。维护一个占用空间为 k 的优先队列。如果当前堆不满,直接添加。当堆长度为 k 的时候,则需要动态更新堆顶元素。占用的空间较小。实现代码如下,供参考。
通过代码
系统函数算法
复制代码
堆解法
复制代码
总结
系统函数排序,也就是快速排序的解法的时间复杂度是 O(n log n), 空间复杂度是 O(log n)
优先队列解法的时间复杂度是 O(n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/4b7119f620803bf75f78c47a2】。文章转载请联系作者。
评论