文档章节

寻找最大的K个数优化解法一

zongjh
 zongjh
发布于 2014/04/11 07:41
字数 591
阅读 49
收藏 2

 昨天我们说了寻找最大的K个数常规的两种解法,一种使用快速排序,另外一种是部分排序。今天我们介绍一种优化解法,
思想如下:在数组arr中我们进行一趟快速排序,选定key,把数组分为两部分a1,和a2。a1中的元素大于等于key,a2中的元素小于key。这样的话就会有两种可能,第一:a1中的元素个数小于K,所以a1中的元素加上K-a1.length个元素就是数组arr中最大的K个数。第二:a1中的元素个数大于或等于K,则返回a1中最大的K个数。这样不断递归就可以决绝这个问题。
先说说,一次快速排序。我们需要返回两个数组a1,a2,但是java不支持多参返回,所以我们用二维数组做为返回参数。具体代码如下: //           
public static int[][] getArr(int[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        int[][] newArr = new int[2][];
        int key = arr[0];
        List<Integer> list1 = new ArrayList<Integer>(); //首先使用list存储数据
        List<Integer> list2 = new ArrayList<Integer>();
        for (int i=1; i<arr.length; i++) {
            if (arr[i] >= key) {
                list1.add(arr[i]);
            } else {
                list2.add(arr[i]);
            }
        }
        if (list1.size() < list2.size()) { //是数据存储更加均匀
            list1.add(key);
        } else {
            list2.add(key);
        }
        int[] a1 = new int[list1.size()];//创建新的数组
        for (int i=0; i<list1.size(); i++) {//数组赋值
            a1[i] = list1.get(i);
        }
        int[] a2 = new int[list2.size()];
        for (int i=0; i<list2.size(); i++) {
            a2[i] = list2.get(i);
        }
        newArr[0] = a1;//储存大于等于key的元素
        newArr[1] = a2;//存储小于key的元素
        return newArr;
    }
接下来我们就要递归调用了,代码如下,我们在外部声明一个list用来存储符合的数据,声明如下:
static List<Integer> list = new ArrayList<Integer>();
public static void xunzhao(int[] arr, int k) {
        if (arr == null || arr.length == 0 || k < 0) {
            return;
        }
        if (arr.length <= k) {//数据比K小
            for (int i=0; i<arr.length; i++) {
                list.add(arr[i]); //存储数据
            }
            return;
        }
        int[][] newArr = getArr(arr);
        if (newArr[0].length >= k) { //a1的元素个数大于K,
             xunzhao(newArr[0], k); //继续分解
        } else {
            for (int i=0; i<newArr[0].length; i++) {
                list.add(newArr[0][i]); //存储元素
            }
            xunzhao(newArr[1], k-newArr[0].length); //在a2中获取K-a1.length个元素
        }
    }
原帖和源码下载地址

© 著作权归作者所有

下一篇: 寻找最大K个数
zongjh
粉丝 1
博文 39
码字总数 12405
作品 0
东城
程序员
私信 提问
轻松搞定面试中的二叉树题目

求二叉树中的节点个数 2. 求二叉树的深度 3. 前序遍历,中序遍历,后序遍历 4.分层遍历二叉树(按层次从上往下,从左往右) 5. 将二叉查找树变为有序的双向链表 6. 求二叉树第K层的节点个数 ...

亚特兰缇斯
2015/09/10
185
0
Leetcode日记7

(2015/1/2) LeetCode 318 Maximum Product of Word Lengths 题目: 1)求一个字符串数组中,两个不同的字符串的长度乘积的最大值。 2)这两个字符串不能共同拥有同一个字符。(两个字符串的...

fxdhdu
2016/01/03
50
0
ZOJ 3505. Yet Another Set of Numbers 解题报告

    ZOJ 3505:Yet Another Set of Numbers     地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3505     题意:有一个数字集合,集合中的数遵循以下规则...

hoodlum1980
2011/11/10
0
0
数组中第K大的元素

数组中第K大的元素总结 解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(nlogn + k)。 解法2: 如果k很小,比如第五个最大的数,而整个数组的长度非...

王大豆
2015/09/05
286
0
LeetCode 滑动窗口法总结

版权声明:版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/Dbyfreedom https://blog.csdn.net/Dbyfreedom/article/details/89066140 1. 介绍 滑动窗口法,也叫...

dby_freedom
04/07
0
0

没有更多内容

加载失败,请刷新页面

加载更多

只需一步,在Spring Boot中统一Restful API返回值格式与统一处理异常

统一返回值 在前后端分离大行其道的今天,有一个统一的返回值格式不仅能使我们的接口看起来更漂亮,而且还可以使前端可以统一处理很多东西,避免很多问题的产生。 比较通用的返回值格式如下:...

晓月寒丶
昨天
59
0
区块链应用到供应链上的好处和实际案例

区块链可以解决供应链中的很多问题,例如记录以及追踪产品。那么使用区块链应用到各产品供应链上到底有什么好处?猎头悬赏平台解优人才网小编给大家做个简单的分享: 使用区块链的最突出的优...

猎头悬赏平台
昨天
28
0
全世界到底有多少软件开发人员?

埃文斯数据公司(Evans Data Corporation) 2019 最新的统计数据(原文)显示,2018 年全球共有 2300 万软件开发人员,预计到 2019 年底这个数字将达到 2640万,到 2023 年达到 2770万。 而来自...

红薯
昨天
65
0
Go 语言基础—— 通道(channel)

通过通信来共享内存(Java是通过共享内存来通信的) 定义 func service() string {time.Sleep(time.Millisecond * 50)return "Done"}func AsyncService() chan string {retCh := mak......

刘一草
昨天
58
0
Apache Flink 零基础入门(一):基础概念解析

Apache Flink 的定义、架构及原理 Apache Flink 是一个分布式大数据处理引擎,可对有限数据流和无限数据流进行有状态或无状态的计算,能够部署在各种集群环境,对各种规模大小的数据进行快速...

Vincent-Duan
昨天
60
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部