LEETCODE 215. Kth Largest Element in an Array 解题思路分析

题目大意:

数组中的第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

说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=215

解题思路分析:

解法一:排序

先说一种最简单的思路,我们将数组升序排序,然后取得数组倒数第k个数即可。

实现代码:

public int findKthLargest(int[] nums, int k) {
    Arrays.sort(nums);
    return nums[nums.length-k];
}

本解法执行时间为1ms。

Runtime: 1 ms, faster than 99.47% of Java online submissions for Kth Largest Element in an Array.

Memory Usage: 41.3 MB, less than 5.18% of Java online submissions for Kth Largest Element in an Array.


解法二:Heap

相对于解法一稍微复杂一些,但也非常好理解。我们循环数组中的每一个数字,然后使用一个PriorityQueue来保存遍历到的数,当 PriorityQueue 中的元素个数大于k时,我们从Queue中poll出一个元素,该元素应该是Queue中最小的那个。直到遍历完所有数字, PriorityQueue 中保存的应该是数组中前k大的所有数字,并且PriorityQueue中首元素应该是其中最小一个,也就是全局第k大的数字。

实现代码:

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> q = new PriorityQueue<>();
    for(int n : nums){
        q.offer(n);
        if(q.size()>k) q.poll();
    }
    return q.poll();
}

本题解法执行时间为4ms。

Runtime: 4 ms, faster than 70.55% of Java online submissions for Kth Largest Element in an Array.

Memory Usage: 40.8 MB, less than 5.18% of Java online submissions for Kth Largest Element in an Array.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-215-kth-largest-element-in-an-array-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。