文档章节

寻找最大的K个数(二):快排优化和二分搜索

zongjh
 zongjh
发布于 2017/05/16 18:15
字数 1385
阅读 14
收藏 0
点赞 0
评论 0

(总要更好的,等你去发现)

 

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

 

今天继续和大家聊寻找最大的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 (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域名解析

喜欢聊技术或者聊观点,可以加入公号:【花生读书汇】

一起:励志,成长,学习,分享。

【花生读书汇】

© 著作权归作者所有

共有 人打赏支持
zongjh
粉丝 1
博文 38
码字总数 12405
作品 0
东城
程序员
寻找最大的k 个数

寻找最大的K个数 寻找第K大的树: a. 快排, 堆 b. 二分查找 可以全部放进内存, 不可以全部放进内存

Playboy002 ⋅ 2015/07/13 ⋅ 1

玩转算法面试:(三)LeetCode数组类问题

数组中的问题其实最常见。 排序:选择排序;插入排序;归并排序;快速排序 查找:二分查找法 数据结构:栈;队列;堆 …… 如何写出正确的程序 建立一个基础的框架,什么是正确的程序 二分查...

天涯明月笙 ⋅ 2017/09/20 ⋅ 0

一个搞ACM需要掌握的算法

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段:练经典常用...

long0404 ⋅ 2015/06/24 ⋅ 0

Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

记录一些算法实践 目录 Java篇 一、基础算法 七种基础排序 二叉堆 K选取问题 链表判环问题 N皇后问题 两指针扫描算法举例 位运算(求首个bit1,求bit1的个数,寻找奇数项) 最小栈的实现 横纵有...

qcer ⋅ 2017/12/20 ⋅ 0

算法进阶路径

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

暖冰 ⋅ 2016/04/02 ⋅ 1

学习算法之路(转)

路漫漫其修远兮,吾将上下而求索。。。 ======================================================== 转一个搞ACM需要的掌握的算法. 要注意,ACM的竞赛性强,因此自己应该和自己的实际应用联系起...

长平狐 ⋅ 2013/01/06 ⋅ 0

学习算法之路

第一阶段:练经典常用算法,下面的每个算法给我打上十到二十遍,同时自己精简代码, 因为太常用,所以要练到写时不用想,10-15 分钟内打完,甚至关掉显示器都可以把程序打 出来. 1.最短路(Fl...

Yong_Luo ⋅ 2010/06/21 ⋅ 2

28个不得不看的经典编程算法

转载自:28个不得不看的经典编程算法 第一名:Union-find 严格地说,并查集是一种数据结构,它专门用来处理集合的合并操作和查询操作。并查集巧妙地借用了树结构,使得编程复杂度降低到了令人...

xjhznick ⋅ 2014/11/06 ⋅ 0

不懂的概念 171030

其实有六成问题都是来自于对过去学过知识的生疏,其他的则是没接触过的新知识。 171030 scanf函数的返回问题: 171022发起。问题来源于在做pta题的时候,系统总是在提交之后提示我“没有处理...

hastings2k ⋅ 2017/11/22 ⋅ 0

数据结构学习(一)

数据结构与算法 1. 链表与数组。 2. 队列和栈,出栈与入栈。 3. 链表的删除、插入、反向。 4. 字符串操作。 5. Hash表的hash函数,冲突解决方法有哪些。 6. 各种排序:冒泡、选择、插入、希尔...

技术小甜 ⋅ 2017/11/16 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

内存障碍: 软件黑客的硬件视图

此文为笔者近日有幸看到的一则关于计算机底层内存障碍的学术论文,并翻译(机译)而来[自认为翻译的还行],若读者想要英文原版的论文话,给我留言,我发给你。 内存障碍: 软件黑客的硬件视图...

Romane ⋅ 30分钟前 ⋅ 0

SpringCloud 微服务 (七) 服务通信 Feign

壹 继续第(六)篇RestTemplate篇 做到现在,本机上已经有注册中心: eureka, 服务:client、order、product 继续在order中实现通信向product服务,使用Feign方式 下面记录学习和遇到的问题 贰 or...

___大侠 ⋅ 47分钟前 ⋅ 0

001. 深入JVM学习—Java运行流程

1. Java运行流程图 2. Java运行时数据区 3. Java虚拟机栈 栈内存是线程私有的,其生命周期和线程相同; 虚拟机栈描述的是Java方法执行的内存模型:执行一个方法时会产生一个栈帧随后将其保存...

影狼 ⋅ 今天 ⋅ 0

gitee、github上issue标签方案

目录 [TOC] issue生命周期 st=>start: 开始e=>end: 结束op0=>operation: 新建issueop1=>operation: 评审issueop2=>operation: 任务负责人执行任务cond1=>condition: 是否通过?op3=>o......

lovewinner ⋅ 今天 ⋅ 0

浅谈mysql的索引设计原则以及常见索引的区别

索引定义:是一个单独的,存储在磁盘上的数据库结构,其包含着对数据表里所有记录的引用指针. 数据库索引的设计原则: 为了使索引的使用效率更高,在创建索引时,必须考虑在哪些字段上创建索...

屌丝男神 ⋅ 今天 ⋅ 0

String,StringBuilder,StringBuffer三者的区别

这三个类之间的区别主要是在两个方面,即运行速度和线程安全这两方面。 首先说运行速度,或者说是, 1.执行速度 在这方面运行速度快慢为:StringBuilder(线程不安全,可变) > StringBuffer...

时刻在奔跑 ⋅ 今天 ⋅ 0

java以太坊开发 - web3j使用钱包进行转账

首先载入钱包,然后利用账户凭证操作受控交易Transfer进行转账: Web3j web3 = Web3j.build(new HttpService()); // defaults to http://localhost:8545/Credentials credentials = Wallet......

以太坊教程 ⋅ 今天 ⋅ 0

Oracle全文检索配置与实践

Oracle全文检索配置与实践

微小宝 ⋅ 今天 ⋅ 0

mysql的分区和分表

1,什么是mysql分表,分区 什么是分表,从表面意思上看呢,就是把一张表分成N多个小表,具体请看mysql分表的3种方法 什么是分区,分区呢就是把一张表的数据分成N多个区块,这些区块可以在同一...

梦梦阁 ⋅ 今天 ⋅ 0

exception.ZuulException: Forwarding error

错误日志 com.netflix.zuul.exception.ZuulException: Forwarding error Caused by: com.netflix.hystrix.exception.HystrixRuntimeException: xxx timed-out and no fallback available. Ca......

jack_peng ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部