编程语言
发布时间:2022-06-26 发布网站:大佬教程 code.js-code.com
大佬教程收集整理的这篇文章主要介绍了【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
描述有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。
给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
![【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大 【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大](http://code.js-code.com/res/2022/06-26/12/febbf3f12a211fabb0a06e57a448ef3a.jpg)
方法:快速排序+找到位置就返回
@H_
674_14@
import java.uti
l.*
;
public class Solution {
public int findKth(
int[] a,
int n,
int K) {
//第k大就是n-k小
quickSort(a, 0, n - 1, n -
K);
return a[n -
K];
}
public void quickSort(
int[] a,
int low,
int high,
int K) {
if(low >= high)
return;
int i = low, j =
high;
int pivot =
a[low];
while(i <
j) {
while(i < j && a[j] >
pivot) {
j--
;
}
if(i <
j) {
a[i++] =
a[j];
}
while(i < j && a[i] <
pivot) {
i++
;
}
if(i <
j) {
a[j--] =
a[i];
}
}
a[i] =
pivot;
//第i就是K的位置,表示找到了最终位置,即可返回
if(K ==
i) {
return;
}
quickSort(a, low, i - 1
, K);
quickSort(a, i + 1
, high, K);
}
}
大佬总结
以上是大佬教程为你收集整理的【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大全部内容,希望文章能够帮你解决【每日一题】【找到位置返回&升序数组中第K大就是n-K小】2022年1月17日-NC88 寻找第K大所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。