寻找最大的K个数（二）：快排优化和二分搜索

（总要更好的，等你去发现）

如果对技术不感兴趣的，可以直接跳转到最后的题外话。写了一点点，支离破碎。也是从这个程序想到的一点点。

今天继续和大家聊寻找最大的k个数。

先来熟悉一下问题：

有很多个无序的数（我们这里假设为正整数），而且各不相等，怎么选出最大的k个数。

例如：2，5，7，1，3，9，3，6，7，8，5

最大的5个数为：7，9，6，7，8

昨天我们给出了两个解法：

快速排序和选择排序，文章详情：寻找最大的k个数：快排和选择（一）

今天我们继续。

回想一下快速排序，每次做完一次快速排序，数组s都会被分成两部分sa和sb。sb的每一个数都大于sa的每一个数。这时候会出现两种情况：

第一：sb.length>=k，这时候我们只需要关心sb数组即可，因为前k个最大的数都在sb中。

第二：sb.length

下面这段代码，是在前面快速排序的基础上修改的。主要是一次快速排序后比较k和

sb数组的长度。

具体代码如下：

packagecom.xylx.utils.selectk;

/**

*优化快速排序，查找最大的ｋ个输

*/

publicclassoptquicksortselectk{

publicstaticvoidmain(string[]args){

int[]arr=constans.getlengtharr(100);

system.out.println("排序前：");

constans.printarr(arr);

optquicksort(arr,0,arr.length-1,constans.k);

system.out.println("排序后:");

constans.printarr(arr);

system.out.println("排序是否正确:"+constans.isok(arr));

constans.selectk(arr);

}

publicstaticvoidoptquicksort(int[]arr,intstart,intend,intk){

intleft=start;

intright=end;

intkey=arr[left];

while(left

while(leftkey){

right--;

}

if(left

inttmp=arr[left];

arr[left]=arr[right];

arr[right]=tmp;

left++;

}

while(left

left++;

}

if(left

inttmp=arr[right];

arr[right]=arr[left];

arr[left]=tmp;

right--;

}

}

if(start

intrightlength=end-right+1;

system.out.println("rightlength="+rightlength+"k="+k);

if(rightlength

optquicksort(arr,start,left-1,k-rightlength);//需要左边数组k-rightlength个最大的数

}

}

if(right+1

intrightlength=end-right+1;

if(rightlength>k){

optquicksort(arr,right+1,end,k);

}

}

}

}

上面这段代码能大大降低排序的次数。

寻找前k个最大数，也就是选择第k大的数。

如果数组s的中最大值为max，最小值为min。那么第k大的值vk一定满足下面的关系：

min<=vk<=max。

我们从中间值开始找起，mid=(min+max)/2。查找数组s中所有>=mid的数的个数total。这时候也会出现两种情况：

第一：total>=k,证明查找出来的数比k多，我们需要增加mid的值，也就是min=mid。

第二：total

这样不断循环，直到max-min<=1。

代码如下：

packagecom.xylx.utils.selectk;

importjava.util.arraylist;

importjava.util.list;

/**

*/

publicclassbinsearchselectk{

publicstaticvoidmain(string[]args){

int[]arr=constans.getlengtharr(100);

constans.printarr(arr);

selectk(arr);

}

publicstaticvoidselectk(int[]arr){

listresult=getmaxmin(arr);

intmax=result.get(0);

intmin=result.get(1);

while(max-min>1){

intmid=(max+min)/2;

inttotal=getgttotal(arr,mid);

if(total>=constans.k){

min=mid;

}else{

max=mid;

}

}

system.out.println("min="+min+"max="+max);

printk(arr,min);

}

privatestaticvoidprintk(int[]arr,intmin){

intindex=0;

system.out.println("最大的k个数:");

for(inti=0;i

if(arr[i]>min){

system.out.print(arr[i]+"");

index++;

}

}

for(inti=0;i<(constans.k-index);i++){

system.out.print(min+"");

}

}

/**

*查找数组中大于等于mid值大的数的个数

*@paramarr

*@parammid

*@return

*/

publicstaticintgetgttotal(int[]arr,intmid){

inttotal=0;

for(inti=0;i

if(arr[i]>=mid){

total++;

}

}

returntotal;

}

/**

*寻找数组中最大值和最小值

*@paramarr

*@return0:最大1:最小

*/

publicstaticlistgetmaxmin(int[]arr){

listresult=newarraylist();

if(arr==null||arr.length<1){

returnresult;

}

intmax=integer.min_value;

intmin=integer.max_value;

for(inti=0;i

if(arr[i]>max){

max=arr[i];

}

if(arr[i]

min=arr[i];

}

}

result.add(max);

result.add(min);

returnresult;

}

}

当循环结束之后，你会得到一个区间min和max。min就是查找的第k大的数。这里需要注意一下，min可能会有多个，不是所有的min都符合要求，所以我们应该先查找比min大的数，查找到的数不够k个，就用min来补齐。

题外话：

总有最好的，等你去发现。就像这个程序，寻找一下还是有更好解法的。

有时候，坑你的不是别人，而是自己。当我们解决一个问题之后，往往都会停留下来，很少能够主动想一想还有没有更好的方法。也就是最近比较流行的：呆在自己的舒适区。

自己给自己挖坑往往是最隐秘的。我们或多或少都在自己挖的坑里，有的舒服，有的痛苦。

舒服的一方就像温水煮蛙里那只还很舒服的青蛙。痛苦的是那只已经快被煮熟的青蛙。

一个问题，通常都会有好多个解法，而我们总是浅尝辄止。一份工作通常都有更优的解法，而我们总是去选择忽略。

所以，没事别忘了虐一虐自己，问一问自己：

是否在自己的舒适区呆太久了！！！

那些年虐我们的面试题：

寻找最大的k个数：快排和选择（一）

靠谱的tcp：三次握手和四次挥手

cdn知道为什么是你？

dns域名解析