一道寻找第K大数字的面试题
程序员文章站
2022-06-19 08:45:30
前言前几天看到一道这样一道面试题,在数组中,寻找第k大的值,我们看到这一道题,我们最先想到的就说直接排序,我们可以采用快速排序,时间复杂度能达到O(nlogn),空间复杂度能达到O(1)。但是我们并不需要把所有的数组排好序,所以我们可以在快速排序的基础上做一点调整。思路实现的原理是这样子的:首先我们找一个基准数,就和快速排序一样,接着把小于基准数的元素移动到数组左边,接着把大于基准数的元素移动到数组右边,这时候,基准数的下标肯定在对应的位置上,也就是第i+1大的数,所以只需要判断当前位置的数与k的大小...
前言
前几天看到一道这样一道面试题,在数组中,寻找第k大的值,我们看到这一道题,我们最先想到的就说直接排序,我们可以采用快速排序,时间复杂度能达到O(nlogn),空间复杂度能达到O(1)。但是我们并不需要把所有的数组排好序,所以我们可以在快速排序的基础上做一点调整。
思路
实现的原理是这样子的:首先我们找一个基准数,就和快速排序一样,接着把小于基准数的元素移动到数组左边,接着把大于基准数的元素移动到数组右边,这时候,基准数的下标肯定在对应的位置上,也就是第i+1大的数,所以只需要判断当前位置的数与k的大小就可以了。如果i+1等于k,说明找到了;如果i+1小于k,则说明我们要找的k正在数组的左部分;如果i+1大于k,则说明我们要找的k正在数组的右部分。
直接上代码!!!
package interview;
/**
* @author xing xing
*/
public class KNumber {
public static void main(String[] args) {
//定义数组
int [] array = {2,7,100,51,-1,20,21};
//求第k大的值
findK(array, 0, array.length - 1, 7);
}
public static void findK(int [] array,int begin,int end,int k) {
int i = partition(array,begin,end);
//由于下标是从0开始,所以我们i+1
//当第i+1的位置大于k的位置时,我们就去左半部分找
if (i+1>k) {
findK(array,begin,i-1,k);
//当第i+1的位置小于k的位置时,我们就去右半部分找
}else if (i+1<k) {
findK(array,i+1,end,k);
}else {
//如果i+1等于k说明我们找到了
System.out.println("第K大值为:"+array[i]);
return ;
}
}
//找到i的位置
public static int partition(int [] array,int begin,int end) {
if(begin < end) {
int key = array[begin];
while(begin < end) {
while (begin < end && key < array[end]){
end--;
}
if (begin < end) {
array[begin] = array[end];
begin++;
}
while (key > array[begin] && begin < end) {
begin++;
}
if (begin < end) {
array[end] = array[begin];
end--;
}
}
array[begin] = key;
}
return begin;
}
}
总结
下面我们分析一下性能,首先空间复杂度为O(1),时间复杂度为O(n),性能非常好,不过这个算法有点绕,需要多多理解。
本文地址:https://blog.csdn.net/qq_42627977/article/details/109965315