(总要更好的,等你去发现)
如果对技术不感兴趣的,可以直接跳转到最后的题外话。写了一点点,支离破碎。也是从这个程序想到的一点点。
今天继续和大家聊寻找最大的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 && arr[right] > key) {
right –;
}
if (left < right) {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left ;
}
while (left<right && arr[left] < key) {
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<k,证明查找出来的数比k少,我们需要减少max的值,也就是max=mid。
这样不断循环,直到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<integer> 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; i<arr.length; 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<arr.length; i ) {
if (arr[i] >= mid) {
total ;
}
}
return total;
}
/
* 寻找数组中最大值和最小值
* @param arr
* @return 0:最大 1:最小
*/
public static list<integer> getmaxmin(int[] arr) {
list<integer> result = new arraylist<integer>();
if (arr == null || arr.length < 1) {
return result;
}
int max = integer.min_value;
int min = integer.max_value;
for (int i=0; i<arr.length; i ) {
if (a
中国生活O2O十五年沉浮录备案申请退回咨询-备案平台新人对于域名注册商该怎么去选择?阿里云服务器必须进行备案吗3大主流视频平台的VIP会员成长体系!腾讯云服务器镜像还原怒江云服务器租用购买阿里云怎么购买高防服务器