算法题：数组中的第k个最大元素

密斯特七少 發表於 2025-6-5 09:00:00

力扣链接
<h2 id="题意">题意</h2>
给定整数数组 <code>nums</code> 和整数 <code>k</code>，请返回数组中第 <code>k</code> 个最大的元素。
请注意，你需要找的是数组排序后的第 <code>k</code> 个最大的元素，而不是第 <code>k</code> 个不同的元素。
你必须设计并实现时间复杂度为 <code>O(n)</code> 的算法解决此问题。
示例 1:
输入: <code>,</code> k = 2 
输出: 5
示例 2:
输入: <code>,</code> k = 4 
输出: 4
提示：
<ul>
<li><code>1 <= k <= nums.length <= 105</code></li>
<li><code>-104 <= nums <= 104</code></li>
</ul>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="堆排序">堆排序</h3>
这道题就是经典的 <code>topK</code> 问题， 实现一个小根堆，规定堆的元素大小是 <code>k</code> 个，将比堆顶大的元素进堆。最后遍历完数组之后，此时堆顶是 <code>k</code> 个元素中最小的，有就是所有元素中第 <code>k</code> 大的了。
可以用PriorityQueue的最小堆来实现：
<pre><code class="language-java">public class KthLargestMinHeap {
public int findKthLargest(int[] nums, int k) {
 PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

 for (int num : nums) {
 if (minHeap.size() < k) {
 minHeap.offer(num);
 } else if (num > minHeap.peek()) {
 minHeap.poll();
 minHeap.offer(num);
 }
 }
 return minHeap.peek();
}
}
</code></pre>
<h3 id="升序排序后索引为-len---k-的元素">升序排序后索引为 len - k 的元素</h3>
其实题目已经告诉我们了：
<blockquote>
你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
</blockquote>
因此，升序排序以后，返回索引为 len - k 这个元素即可。
代码如下：
<pre><code class="language-java">public class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        Arrays.sort(nums);
        return nums;
    }
}
</code></pre>
<ul>
<li>时间复杂度：O(NlogN)。这里 N 是数组的长度，算法的性能消耗主要在排序，JDK 默认使用快速排序，因此时间复杂度为O(NlogN)。</li>
<li>空间复杂度：O(1)。这里是原地排序，没有借助额外的辅助空间。</li>
</ul>
但是，如果出了这道题，显然不是想让你调 API ，而是看你对快排的理解
<h3 id="借助快排-partition-操作定位推荐">借助快排 partition 操作定位（推荐）</h3>
“快速排序” 中的 partition(切分)操作简单介绍如下：
<ul>
<li>对于某个索引i，nums 已经排序完，即 nums 经过 partition(切分)操作以后会放置在它 “最终应该放置的地方”；</li>
<li>nums 到 nums 中的所有元素都不大于 nums；</li>
<li>nums 到 nums 中的所有元素都不小于 nums。</li>
</ul>
很显然，nums 最终所在的位置，也就是它排序后的具体位置。也就是说，如果实现的排序是降序排序，那么第k个位置的数据，也确定就是第k大的
而这样每经过一次 partition操作就能缩小搜索的范围，这样的思想叫做 “减而治之”(是 “分而治之” 思想的特例)。下面是参考代码：
<pre><code class="language-javascript">public class Solution {

    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;

        // 转换一下，第 k 大元素的索引是 len - k
        int target = len - k;

        while (true) {
            int index = partition(nums, left, right);
            if (index == target) {
                return nums;
            } else if (index < target) {
                left = index + 1;
            } else {
                right = index - 1;
            }
        }
    }

public static int partition(int[] array, int low, int high) {
 // 取最后一个元素作为中心元素
 int pivot = array;
 // 定义指向比中心元素大的指针，首先指向第一个元素
 int pointer = low;
 // 遍历数组中的所有元素，将比中心元素大的放在右边，比中心元素小的放在左边
 for (int i = low; i < high; i++) {
 if (array <= pivot) {
 // 将比中心元素小的元素和指针指向的元素交换位置
 // 如果第一个元素比中心元素小，这里就是自己和自己交换位置，指针和索引都向下一位移动
 // 如果元素比中心元素大，索引向下移动，指针指向这个较大的元素，直到找到比中心元素小的元素，并交换位置，指针向下移动
 swap(array, i, pointer);
 pointer++;
 }
 }
 // 将中心元素和指针指向的元素交换位置
 swap(array, pointer, high);
 return pointer;
}

private static void swap(int[] arr, int i, int j) {
int temp = arr;
arr = arr;
arr = temp;
}
}
</code></pre>
<ul>
<li>时间复杂度：O(N)。这里 N 是数组的长度。</li>
<li>空间复杂度：O(1)。切分过程可以不借助额外的数组空间，仅通过交换数组元素实现，没有借助额外的辅助空间。</li>
</ul>

</div>
<div id="MySignature" role="contentinfo">
本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top 
来源：https://www.cnblogs.com/sevencoding/p/18905510

頁: [1]

琼殿技术论坛's Archiver

算法题：数组中的第k个最大元素