leetcode
leetcode 151 ~ 200
数组中的第K个最大元素

数组中的第K个最大元素

难度:

标签:

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

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

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 1:

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

示例 2:

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

 

提示：

  • 1 <= k <= nums.length <= 105
  • -104 <= nums[i] <= 104

代码结果

运行时间: 61 ms, 内存: 27.1 MB

/*
 * Problem: Given an integer array nums and an integer k, return the kth largest element in the array.
 * You need to find the kth largest element in the sorted order, not the kth distinct element.
 * You must implement a solution with O(n) time complexity.
 */
 
import java.util.Arrays;
 
public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Sort the array using Java Streams in descending order
        return Arrays.stream(nums)
                     .boxed()
                     .sorted((a, b) -> b - a)
                     .limit(k)
                     .skip(k - 1)
                     .findFirst()
                     .get();
    }
}

解释

方法:

这个题解使用了快速选择（QuickSelect）算法来找到数组中第k大的元素。其基本思路是：通过随机选择一个基准元素 pivot，将数组划分为三个部分：大于 pivot 的元素、小于 pivot 的元素和等于 pivot 的元素。根据这三部分元素的数量，可以确定第 k 大的元素在哪个部分中，然后递归地在相应的部分继续查找，直到找到第 k 大的元素。

时间复杂度:

O(n)

空间复杂度:

O(log n)

代码细节讲解

🦆
为什么在快速选择算法中选择随机元素作为基准（pivot）有助于避免最坏情况的发生？
▷
在快速选择算法中，如果总是选择固定位置的元素作为基准，如始终选择第一个元素或最后一个元素，当输入数组已经有序或接近有序时，算法性能会退化到O(n^2)。通过随机选择基准元素，可以使算法对于不同的输入在平均情况下表现更加稳定，大大减少了遭遇最坏情况的概率，从而确保算法在大多数情况下都能维持较好的性能（平均时间复杂度为O(n)）。
🦆
快速选择算法在确定每一步的基准元素后，是如何确保递归调用的深度保持在O(log n)的平均情况下？
▷
快速选择算法通过每次递归减少搜索的数组的大小来保证递归深度。因为每次都是随机选择基准元素，平均情况下，数组会被分成大小大致相等的两部分。这样每次递归都会排除约一半的元素，递归深度因此在平均情况下达到O(log n)。
🦆
在题解中，当len(big) >= k时，为什么直接递归搜索big数组而不是考虑equal数组中的元素？
▷
当len(big) >= k时，这意味着所有在big数组中的元素都比pivot大，并且数量足以包含第k大的元素。因此，第k大的元素肯定不在equal数组中，这使得搜索可以直接在big数组中继续进行，无需考虑equal数组，从而提高了算法的效率。
🦆
题解中提到的‘第 k 大的元素是 pivot’的判断条件是否准确？是否应该是len(nums) - len(small) - len(equal) < k <= len(nums) - len(small)？
▷
是的，题解中的条件表述有误。正确的判断应该是：当big数组的长度小于k且当加上equal数组的长度后，k仍然不超过big数组和equal数组长度之和时，说明第k大的元素在equal数组中，且等于pivot。因此，正确的条件应该是len(nums) - len(small) - len(equal) < k <= len(nums) - len(small)。

相关问题

摆动排序 II

给你一个整数数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

你可以假设所有输入数组都可以得到满足题目要求的结果。

 

示例 1：

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]
解释：[1,4,1,5,1,6] 同样是符合题目要求的结果，可以被判题程序接受。

示例 2：

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

 

提示：

  • 1 <= nums.length <= 5 * 104
  • 0 <= nums[i] <= 5000
  • 题目数据保证，对于给定的输入 nums ，总能产生满足题目要求的结果

 

进阶：你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？

前 K 个高频元素

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

 

提示：

  • 1 <= nums.length <= 105
  • k 的取值范围是 [1, 数组中不相同的元素的个数]
  • 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

第三大的数

给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。

 

示例 1：

输入：[3, 2, 1]
输出：1
解释：第三大的数是 1 。

示例 2：

输入：[1, 2]
输出：2
解释：第三大的数不存在, 所以返回最大的数 2 。

示例 3：

输入：[2, 2, 3, 1]
输出：1
解释：注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。

 

提示：

  • 1 <= nums.length <= 104
  • -231 <= nums[i] <= 231 - 1

 

进阶：你能设计一个时间复杂度 O(n) 的解决方案吗？

数据流中的第 K 大元素

设计一个找到数据流中第 k 大元素的类（class）。注意是排序后的第 k 大元素，不是第 k 个不同的元素。

请实现 KthLargest 类：

  • KthLargest(int k, int[] nums) 使用整数 k 和整数流 nums 初始化对象。
  • int add(int val) 将 val 插入数据流 nums 后，返回当前数据流中第 k 大的元素。

 

示例：

输入：
["KthLargest", "add", "add", "add", "add", "add"]
[[3, [4, 5, 8, 2]], [3], [5], [10], [9], [4]]
输出：
[null, 4, 5, 5, 8, 8]

解释：
KthLargest kthLargest = new KthLargest(3, [4, 5, 8, 2]);
kthLargest.add(3);   // return 4
kthLargest.add(5);   // return 5
kthLargest.add(10);  // return 5
kthLargest.add(9);   // return 8
kthLargest.add(4);   // return 8

 

提示：
  • 1 <= k <= 104
  • 0 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • -104 <= val <= 104
  • 最多调用 add 方法 104 次
  • 题目数据保证，在查找第 k 大元素时，数组中至少有 k 个元素

最接近原点的 K 个点

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

 

示例 1：

输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释： 
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

 

提示：

  • 1 <= k <= points.length <= 104
  • -104 < xi, yi < 104
最短回文串组合总和 III