leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现 ...

LeetCode 215.数组中的第K个最大元素

标题形貌

给定一个整数数组 nums 和一个整数 k，请返回数组中第 k 个最大的元素。
请留意，要求排名是从大到小的，因此第 k 个最大元素是排序后的第 k 个元素。你需要计划一个高效的算法来办理这个问题。
示例 1：
输入：nums = [3,2,1,5,6,4], k = 2
输出：5
表明：数组中第二大的元素是 5。
示例 2：
输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4
表明：数组中第四大的元素是 4。
Java 实今世码

1. class Solution {
2.     public int findKthLargest(int[] nums, int k) {
3.         // 使用最小堆来找第k大的元素
4.         PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
6.         for (int num : nums) {
7.             minHeap.offer(num);
8.             if (minHeap.size() > k) {
9.                 minHeap.poll(); // 维护堆的大小为k，去除堆中最小的元素
10.             }
11.         }
13.         return minHeap.peek(); // 最小堆的根就是第k大的元素
14.     }
15. }

复制代码

解题思绪

   

• 最小堆方法： 我们可以利用最小堆（PriorityQueue）来实现。堆是一个完全二叉树，可以在 O(logn) 时间内进行插入和删除操作。
  
  
  
  • 将数组中的前 k 个元素插入到最小堆中。
    
  • 如果当前堆中元素个数大于k，则吐出。
    
  • 最后，堆顶的元素就是第 k 大的元素。
    
  这种方法的时间复杂度是 O(n log k)，其中 n 是数组的大小，k 是需要找到的第 k 大元素。
  
  
• 快速选择法： 另一种方法是使用快速排序的思想，即快速选择（Quickselect）。通过对数组进行划分，选择性地进入有大概包含第 k
  大元素的子数组。这个方法的平均时间复杂度是 O(n)。
  

  复杂度分析

   

• 时间复杂度: 使用最小堆方法时，插入一个元素的时间复杂度是 O(log k)，所以对于数组中 n 个元素，总的时间复杂度是 O(n log k)。
  
• 空间复杂度: O(k)，因为堆中最多存储 k 个元素。
  

  举例阐明执行过程

   假设有数组 nums = [3,2,1,5,6,4]，我们要求第 2 大的元素。
  

• 初始数组：[3,2,1,5,6,4]，k = 2
  
• 创建一个大小为 2 的最小堆：
  
  
  
  • 插入 3，堆为 [3]
    
  • 插入 2，堆为 [2, 3]（因为堆是最小堆，所以自动调整）
    
  • 插入 1，堆为 [1, 3]（删除最小元素 2）
    
  • 插入 5，堆为 [3, 5]（删除最小元素 1）
    
  • 插入 6，堆为 [5, 6]（删除最小元素 3）
    
  • 插入 4，堆为 [5, 6]（删除最小元素 4）
    
  
  
• 终极堆中元素为 [5, 6]，堆顶为 5，即第 2 大元素。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。