(总要更好的,等你去发现)
如果对技术不感兴趣的,可以直接跳转到最后的题外话。写了一点点,支离破碎。也是从这个程序想到的一点点。
今天继续和大家聊寻找的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;
/**
* 优化快速排序,查找的K个输
*/
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
right --;
}
if (left < right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left ++;
}
while (left left ++; } 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) { //右边数组小于需要的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 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; i if (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; i if (arr[i] >= mid) { total++; } } return total; } /** * 寻找数组中值和最小值 * @param arr * @return 0: 1:最小 */ public static List List if (arr == null || arr.length < 1) { return result; } int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for (int i=0; i if (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个数(二):快排优化和二分搜索
URL链接:http://bjjierui.cn/article/chscoj.html