（总要更好的，等你去发现）
玉林网站制作公司哪家好，找创新互联！从网页设计、网站建设、微信开发、APP开发、
成都响应式网站建设公司等网站项目制作，到程序开发，运营维护。创新互联自2013年创立以来到现在10年的时间，我们拥有了丰富的建站经验和运维经验，来保证我们的工作的顺利进行。专注于网站建设就选创新互联。
如果对技术不感兴趣的，可以直接跳转到最后的题外话。写了一点点，支离破碎。也是从这个程序想到的一点点。
今天继续和大家聊寻找的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，这时候前K个的数为Sb加上Sa数组中前K-Sb.length个数。
下面这段代码，是在前面快速排序的基础上修改的。主要是一次快速排序后比较K和
Sb数组的长度。
具体代码如下：
package com.xylx.utils.selectK;
/**
* 优化快速排序，查找的Ｋ个输
*/
public class OptQuickSortSelectK {
public static void main(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);
}
public static void optQuickSort(int[] arr, int start, int end, int k) {
int left = start;
int right = end;
int key = arr[left];
while (left < right) {
while (left key) {
right --;
}
if (left < right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left ++;
}
while (leftleft ++;
}
if (left < right) {
int tmp = arr[right];
arr[right] = arr[left];
arr[left] = tmp;
right--;
}
}
if (start < left-1) {
int rightLength = end - right + 1;
System.out.println("rightLength="+rightLength+" k="+k);
if (rightLength < k) { //右边数组小于需要的Ｋ数
optQuickSort(arr, start, left-1, k-rightLength); //需要左边数组k-rightLength个的数
}
}
if (right + 1 < end) {
int rightLength = 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。
代码如下：
package com.xylx.utils.selectK;
import java.util.ArrayList;
import java.util.List;
/**
*/
public class BinSearchSelectK {
public static void main(String[] args) {
int[] arr = Constans.getLengthArr(100);
Constans.printArr(arr);
selectK(arr);
}
public static void selectK(int[] arr) {
List result = getMaxMin(arr);
int max = result.get(0);
int min = result.get(1);
while (max - min > 1) {
int mid = (max + min)/2;
int total = getGTTotal(arr, mid);
if (total >= Constans.K) {
min = mid;
} else {
max = mid;
}
}
System.out.println("min="+min+" max="+max);
printK(arr, min);
}
private static void printK(int[] arr, int min) {
int index = 0;
System.out.println("的K个数:");
for (int i=0; iif (arr[i] > min) {
System.out.print(arr[i]+" ");
index++;
}
}
for (int i=0; i<(Constans.K-index); i++) {
System.out.print(min+" ");
}
}
/**
* 查找数组中大于等于mid值大的数的个数
* @param arr
* @param mid
* @return
*/
public static int getGTTotal(int[] arr, int mid) {
int total = 0;
for (int i=0; iif (arr[i] >= mid) {
total++;
}
}
return total;
}
/**
* 寻找数组中值和最小值
* @param arr
* @return 0: 1:最小
*/
public static List getMaxMin(int[] arr) {
List result = new ArrayList();
if (arr == null || arr.length < 1) {
return result;
}
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for (int i=0; iif (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
result.add(max);
result.add(min);
return result;
}
}
当循环结束之后，你会得到一个区间min和max。min就是查找的第K大的数。这里需要注意一下，min可能会有多个，不是所有的min都符合要求，所以我们应该先查找比min大的数，查找到的数不够K个，就用min来补齐。
题外话：
总有最好的，等你去发现。就像这个程序，寻找一下还是有更好解法的。
有时候，坑你的不是别人，而是自己。当我们解决一个问题之后，往往都会停留下来，很少能够主动想一想还有没有更好的方法。也就是最近比较流行的：呆在自己的舒适区。
自己给自己挖坑往往是最隐秘的。我们或多或少都在自己挖的坑里，有的舒服，有的痛苦。
舒服的一方就像温水煮蛙里那只还很舒服的青蛙。痛苦的是那只已经快被煮熟的青蛙。
一个问题，通常都会有好多个解法，而我们总是浅尝辄止。一份工作通常都有更优的解法，而我们总是去选择忽略。
所以，没事别忘了虐一虐自己，问一问自己：
是否在自己的舒适区呆太久了！！！
那些年虐我们的面试题：
寻找的K个数：快排和选择（一）
靠谱的TCP：三次握手和四次挥手
CDN知道为什么是你？
DNS域名解析
网站栏目：寻找的K个数（二）：快排优化和二分搜索
标题网址：http://www.cdkjz.cn/article/chscoj.html
