文档章节

寻找最大K个数

zongjh
 zongjh
发布于 2014/04/09 21:19
字数 415
阅读 12
收藏 0

 寻找最大的K个数,这个是面试中比较常见的一道题,网上也有很多例子,在这里先写一些比较传统的解法,以后会更新到比较好的算法。
这个题拿到之后首先会想到排序,排好序之后在选取选取最大的K个数。排序选择快速排序是个比较好的选择。
好了,让我们来进行第一个解法:快速排序
代码如下
public static void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int key = arr[start];
            int right = start;
            int left = end;
            while (right < left) {
                while (right < left && arr[left] > key) {
                    left --;
                }
                if (right < left) {
                    arr[right] = arr[left];
                }
                while (right < left && arr[right] <= key) {
                    right ++;
                }
                if (right < left) {
                    arr[left] = arr[right];
                }
            }
            arr[right] = key;
            quickSort(arr, start, right-1);
            quickSort(arr, left+1, end);
        }
    }
快速排序之后,数组会是有序的,上面的排序是从小到大的,所以我们输出应该是下面这样
                int k = 4;
        for (int i=arr.length-1; i>=arr.length-k; i--) {
            System.out.println(arr[i]+"  ");
        }
。第一个解法已经好了,但是有没有更好的办法。
答案是有的!我们可以选择部分排序,接下来我们使用选择排序来做解决这个问题。
代码如下:
public static int[] selectSortK(int[] arr, int k) {
        if(arr == null || arr.length == 0) {
            return null;
        }
        int[] newArr = new int[k];
        List<Integer> list = new ArrayList<Integer>();//记录每次最大数的下标
        for (int i=0; i<k; i++) {
            int maxValue = Integer.MIN_VALUE; //最大值
            int maxIndex = i;
            for (int j=0; j<arr.length; j++) {
                if (arr[j] > maxValue && !list.contains(j) ) {
                    maxValue = arr[j];
                    maxIndex = j;
                }
            }
            if (!list.contains(maxIndex)) {//如果不存在,就加入
                list.add(maxIndex);
                newArr[i] = maxValue;
            }
        }
        return newArr;
    }
源码下载源码下载

© 著作权归作者所有

zongjh
粉丝 1
博文 39
码字总数 12405
作品 0
东城
程序员
私信 提问
找出无序数组中最小的k个数(top k问题)

给定一个无序的整型数组arr,找到其中最小的k个数 该题是互联网面试中十分高频的一道题,如果用普通的排序算法,排序之后自然可以得到最小的k个数,但时间复杂度高达O(NlogN),且普通的排序算...

群星纪元
04/22
3
0
Algo-Practice: 算法实践(JavaScript & Java),排序,查找、树、两指针、动态规划等

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

qcer
2017/12/20
0
0
如何寻找无序数组中的第K大元素?

如何寻找无序数组中的第K大元素? 有这样一个算法题:有一个无序数组,要求找出数组中的第K大元素。比如给定的无序数组如下所示: 如果k=6,也就是要寻找第6大的元素,很显然,数组中第一大元...

murphy_gb
03/03
0
0
寻找最大的K个数,Top K问题的堆实现

前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。 先拿100...

天天顺利
2018/05/18
87
0
机器学习之主成分分析PCA及代码示例

一、主成分分析(PCA) 主成分分析(Principal Component Analysis)是一种常用的降维算法,可通过线性组合的方法将多个特征综合为少数特征,且综合后的特征相互独立,又可以表示原始特征的大...

cxmscb
2017/03/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OpenStack 简介和几种安装方式总结

OpenStack :是一个由NASA和Rackspace合作研发并发起的,以Apache许可证授权的自由软件和开放源代码项目。项目目标是提供实施简单、可大规模扩展、丰富、标准统一的云计算管理平台。OpenSta...

小海bug
昨天
5
0
DDD(五)

1、引言 之前学习了解了DDD中实体这一概念,那么接下来需要了解的就是值对象、唯一标识。值对象,值就是数字1、2、3,字符串“1”,“2”,“3”,值时对象的特征,对象是一个事物的具体描述...

MrYuZixian
昨天
6
0
数据库中间件MyCat

什么是MyCat? 查看官网的介绍是这样说的 一个彻底开源的,面向企业应用开发的大数据库集群 支持事务、ACID、可以替代MySQL的加强版数据库 一个可以视为MySQL集群的企业级数据库,用来替代昂贵...

沉浮_
昨天
6
0
解决Mac下VSCode打开zsh乱码

1.乱码问题 iTerm2终端使用Zsh,并且配置Zsh主题,该主题主题需要安装字体来支持箭头效果,在iTerm2中设置这个字体,但是VSCode里这个箭头还是显示乱码。 iTerm2展示如下: VSCode展示如下: 2...

HelloDeveloper
昨天
7
0
常用物流快递单号查询接口种类及对接方法

目前快递查询接口有两种方式可以对接,一是和顺丰、圆通、中通、天天、韵达、德邦这些快递公司一一对接接口,二是和快递鸟这样第三方集成接口一次性对接多家常用快递。第一种耗费时间长,但是...

程序的小猿
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部