215 数组中的第k个最大元素

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

示例1：

1 2	输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

示例2：

1 2	输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

说明：

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

代码实现：

public int findKthLargest(int[] nums, int k) {
       if (nums.length == 0 || k < 0 || k > nums.length) {
           return -1;
       }
       PriorityQueue<Integer> heap = new PriorityQueue<>();
       for (int val : nums) {
           heap.offer(val);
           if (heap.size() > k) {
               heap.poll();
           }
       }
       return heap.peek();
   }

思路：

1	PriorityQueue 时间复杂度为 Nlog(K),空间复杂度为K

215 数组中的第k个最大元素

近期文章

近期评论

标签

热门

文章归档

分类目录

功能