大佬教程收集整理的这篇文章主要介绍了leetcode 215. Kth Largest Element in an Array 数组中的第K个最大元素,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
https://leetcode.cn/problems/kth-largest-element-in-an-array
给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。** ** 示例 1:@H_197_6@
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:@H_197_6@
提示:@H_197_6@
理解题意:@H_197_6@ 在一个未排序的数组中,找到第k大的数字。输入一个数组和一个目标k,输出第k大的数字,题目黑夜一定有解。 解题思路:@H_197_6@ 快速选择一般用于解决k-th Element问题,可以在O(n)时间复杂度,O(1)空间复杂度完成求解工作。快速选择的实现和快速排序的实现类似,不过只需要找第k大的(pivort)即可,不需要对其进行左右排序。与快速排序一样,快速选择一般需要先打乱数组,否则最坏情况下时间复杂度为O(n^2)。 解决思路:@H_197_6@ 数组中第k个最大元素其实就是求数组中第nums.length - k个最小元素,我们定义target = nums.length - k。 先找一个中枢点(pivort),然后遍历其他数字,小于pivort的排左边,大于pivort的排右边,中枢点是数组中的第几大的数字就确定了,如果pivort与target相等,直接返回pivort位置的数字,如果大于target,说明要求的数字在左边部分,否则在右边部分。剩下的就是递归了。
public class Solution {
public int findKthLargest(int[] nums, int k) {
int l = 0;
int r = nums.length - 1;
// 第k个大,就是第nums.length - k个小
int target = nums.length - k;
while (l < r) {
int mid = quick@R_696_10288@ction(nums, l, r);
if (mid == target) {
return nums[mid];
}
if (mid > target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return nums[l];
}
/**
* 快速选择
*/
privatE int quick@R_696_10288@ction(int[] nums, int l, int r) {
int i = l + 1;
int j = r;
while (true) {
while (i < r && nums[i] <= nums[l]) {
i++;
}
while (l < j && nums[j] >= nums[l]) {
j--;
}
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}
以上是大佬教程为你收集整理的leetcode 215. Kth Largest Element in an Array 数组中的第K个最大元素全部内容,希望文章能够帮你解决leetcode 215. Kth Largest Element in an Array 数组中的第K个最大元素所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。