题目描述:

在未排序的数组中找到第 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个最大的元素就是前K个元素中最小的元素。

* 构建一个小根堆,堆的大小为K
* 1)当堆的大小小于K的时候,依次向其中加入新元素
* 2)当堆的大小=k 时,下一次每加入一个元素,则先将堆顶元素(最小元素)抛出,
* 最后扫描完这个列表,则堆顶元素(最小值)为第K大的元素 package leetcode; import java.util.Comparator;
import java.util.PriorityQueue; /** * Created by szh on 2020/6/19. * * @author
szh */ public class TOPK_N { public int findKthLargest(int[] nums, int k) { if
(k > nums.length || k == 0) { return -1; } PriorityQueue<Integer> priorityQueue
= new PriorityQueue<>(k, new Comparator<Integer>() { @Override public int
compare(Integer o1, Integer o2) { return -o2.compareTo(o1); } }); for (int i =
0; i < nums.length; i++) { int tmp = nums[i]; if (priorityQueue.size() < k) {
priorityQueue.offer(tmp); } else if (priorityQueue.peek() < tmp) {
priorityQueue.poll(); priorityQueue.offer(tmp); } } // while
(priorityQueue.size() != 1) { // //System.out.println(priorityQueue.poll()); //
priorityQueue.poll(); // } return priorityQueue.poll(); } public static void
main(String[] args) { TOPK_N topk_n = new TOPK_N(); int result_1 =
topk_n.findKthLargest(new int[]{1, 2, 4, 3, 2, 2, 2, 2, 2}, 5);
System.out.println(result_1);
System.out.println("------------------------------");
System.out.println("------------------------------");
System.out.println("------------------------------"); int result_2 =
topk_n.findKthLargest(new int[]{1, 2, 4, 3, 2, 2, 2, 2, 2}, 2);
System.out.println(result_2);
System.out.println("------------------------------");
System.out.println("------------------------------");
System.out.println("------------------------------"); int result_3 =
topk_n.findKthLargest(new int[]{1, 2, 4, 3, 5, 6, 7, 8, 9}, 4);
System.out.println(result_3); } }
 

 

技术
©2019-2020 Toolsou All rights reserved,
LinkedHashMap基本用法&使用实现简单缓存 dedecms网站被黑 劫持到其他网站如何解决苹果不送充填器耳机真为环保?可能还是为了赚钱吧图片格式转换错误总结-myBatis plus 分页numpy:多维数组的创建用C语言做很简单的飞机游戏Keras保存与加载模型(JSON+HDF5)福布斯中国汽车富豪榜:何小鹏第11 李想第14 李斌第15hive大量小文件处理方法总结