215. 数组中的第K个最大元素
1、题目
给定整数数组 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
Related Topics
- 数组
- 分治
- 快速选择
- 排序
- 堆(优先队列)
2、题目分析
借助快排的分治思想,找到区间支点,再判断支点所在位置是否为第k大的位置
3、复杂度最优解代码示例
Integer kNum = null;
public int findKthLargest(int[] nums, int k) {
findKth(nums, k, 0, nums.length - 1);
return kNum == null ? -1 : nums[kNum];
}
public void findKth(int[] nums, int k, int left, int right) {
if (kNum != null || left > right) {
// 退出递归,已找到第k大,或者左指针大于右指针。
return;
}
int leftArgs = left;
int rightArgs = right;
// 支点标识:true-支点为左指针,false-支点为右指针
boolean isLeft = true;
while (left <= right) {
if (nums[left] >= nums[right]) {
// 若左指针数据大于右指针数据,则互换位置,并标识新的支点指针。
// 注:nums[left] == nums[right] 时,从结果角度看,可不互换。但若不互换,在特殊情况,比如数组元素均相等时,时间复杂度会从O(nlogn)退化为O(n²)
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
isLeft = !isLeft;
}
if (isLeft) {
// isLeft=true,表明支点为左指针,此时移动右指针
right--;
} else {
// isLeft=false,表明支点为右指针,此时移动左指针
left++;
}
}
int point = isLeft ? left : right;
if (point == nums.length - k) {
// 判断支点是否为第k大,是则不再递归分治。
kNum = point;
} else if (point > nums.length - k) {
// 支点所在位置大于第k大,故第k大在当前支点的左边区间
findKth(nums, k, leftArgs, point - 1);
} else {
// 支点所在位置小于第k大,故第k大在当前支点的右边区间
findKth(nums, k, point + 1, rightArgs);
}
}
4、适用场景
-
数据分析:在处理大量数据时,找出第K个最大元素可以帮助我们了解数据的分布情况,例如在销售数据中找出销售额排名第K的商品。
-
算法设计:在设计一些需要排序的算法时,如快速排序、堆排序等,找出第K个最大元素可以作为算法的一部分。
-
游戏开发:在一些游戏中,可能需要找出得分排名第K的玩家,这时就需要找出数组中的第K个最大元素。
-
网络编程:在网络编程中,可能需要找出传输速度排名第K的节点,这时也需要找出数组中的第K个最大元素。
-
机器学习:在机器学习中,可能需要找出预测结果排名第K的模型,这时也需要找出数组中的第K个最大元素。
-
数据库查询:在数据库查询中,可能需要找出某个字段值排名第K的记录,这时也需要找出数组中的第K个最大元素。