从100亿个随机数中找到最大的10000个,求算法

从100亿个随机数中找到最大的10000个,求算法。。。。。。。必须要30个字以上

0

8个回答

可以参考map-reduce的方法,先分组,把100亿的数据拆成1000块等,根据你机器的性能,然后分别对这一1000个分块数据,各自进行排序

然后再用归并排序的方式,从这一1000个块中逐步比较最大值,从而得到最大的10000个数据

0

一个是大数,一个寻找最大数,因为数字大所以算法对速度的要求是要比较高的。
所以你需要的算法是必须结合这两样的,大数搜索其实也没有最快的,你可以在排序算法里面进行自己选择修改,我建议可以使用分治的快速搜索,大数可以通过python或者java中的大整数模块进行生成,这样会省事很多。

0

如果随机数是有一定范围的,比如32bit随机int,可以用位图法来做,也就是开一个 0~2^32-1 的数组,遍历数据,并且把对应的那个元素+1
然后从数组从后往前找1000个计数

0

1.如果是随机数不重复,可以直接用TreeSet,自带排序功能,调用API感觉比较省心,就是时间要花一些

2.如果是随机数可能重复,考虑用卷积来做。

0

假设有一个原点(0,0),有100亿个随机数,代表着与(0,0)的距离,然后给他们分配(使用Set,确保每次分配的点都不同)点坐标(相同数值,也得分配不同的点)
以(0,0)为原点,半径为X,X自转,每次X转完一圈,X++,
有一个count变量,
每次扫到一个点,count++

当count的值=9 999 989 999时
记录剩下的10000个点,即为那10000个随机数
这里不考虑,第10000个数字,同时有多个重复的情况

网络卡了。。。。

0

看情况,如果是数据库存储的话,排序时加个top就行,如果是内存处理,这个数据量有点大,但是也就是排序,然后找前面的1000个,当然数组算法效率肯定比链表快,建议使用数组。

-1
-1

看看这篇文章,讲的很清楚:
http://blog.csdn.net/lemon_tree12138/article/details/48783535

-2
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
算法实现:如何从100亿个数中找到最大的10000个数
一看这个这个题目:也许你就蒙了,这么多的数排序,直接读入内存,内存是装不下的,一个解决办法:用堆排序,先取10000个数排序,排序的时间复杂度,nlogn=10000*log1000,设它为T0,那么后面的数据依次取一个和这个堆比较,堆里面永远保留最大的10000个数据,最后就输出这10000w个数据,不知道还有什么好的办法吗?
100亿个数取出最大的10000个
题目:100亿个整数,求最大的1万个数,并说出算法的时间复杂度  算法:如果把100亿个数全部读入内存,需要100 0000 0000 * 4B 大约40G的内存,这显然是不现实的。  我们可以在内存中维护一个大小为10000的最小堆,每次从文件读一个数,与最小堆的堆顶元素比较,若比堆顶元素大,  则替换掉堆顶元素,然后调整堆。最后剩下的堆内元素即为最大的1万个数,算法复杂度为O(NlogN)  
100亿个数字找出最大的10个
1、首先一点,对于海量数据处理,思路基本上是确定的,必须分块处理,然后再合并起来。 2、对于每一块必须找出10个最大的数,因为第一块中10个最大数中的最小的,可能比第二块中10最大数中的最大的还要大。 3、分块处理,再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器,每个服务器又有很多的CPU,因此,100亿个数分成100块,每个服务器处理一块,1亿...
海量数据处理:有1亿个浮点数,找出其中最大的10000个
第一种方法是将数据全部排序,然后在排序后的集合中进行查找,最快的排序算法的时间复杂度一般为O(nlogn),例如快速排序.而在32位机器上,每个float类型占4B,1亿个浮点数就要占用400M的存储空间,对于一些可以内存小于400MB的计算机而言,显然是不能一次将全部数据读入内存进行排序的.其实即使内存能满足要求,该方法也不高效,因为题目的目的是寻找出最大的10000个数即可,而排序是将所有元素...
在存有10亿个数的文件中找到最大的100万个数
这是《编程珠玑》中的一道题目。10亿个整数,假设每个整数需要四个字节,如果使用排序的话,需要大约4G的内存,现在的很多pc都没有多这么内存,更不用说作者那个年代。 我们借助最小堆来解决这个问题。 主要步骤: 一、使用一个大小为一百万零一的整数数组来构建堆(堆的下标从1开始) 二、从文件中读取前一百万个数,每读入一个数,调用函数,保持其最小堆的性质,堆的根永远是堆中最小的元素。 三、从一百
编写算法,从10亿个浮点数当中,选出其中最大的10000个
<br />编写算法,从10亿个浮点数当中,选出其中最大的10000个。<br />用外部排序,在《数据结构》书上有<br />《计算方法导论》在找到第n大的数的算法上加工(注意:先将数据进行分割成数据量小的一些文件,如1000000个数据为一个文件,然后将每个文件数据进行排序,用快速排序法排序,然后使用K路合并法将其合并到一个文件下,取出排序好的最大的10000个数据)<br />另解:(1)读一次所有数据,得出最大和最小。(2)用最大和最小,分100个区间dx = (x_max - x_min) / 1
通过堆排序从1亿个数中找到最小的100个数
package com.my.util; import java.util.Arrays; import java.util.Date; import java.util.Random; public class Top100 { public static void main(String[] args) { find(); } public static void find(
查找1亿个数里面最大的100个数。
#include #include #include #include #include #include #include using namespace std; int main() { vector a(100000000,0); srand((int)time(0)); for(int i=0;i<100000000;i++) {
从一亿个数中找出最大的一万个数
问题定义:         从一亿个数中找出最大的一万个数 不假思索:         拿到这道题,马上就会想到的方法是建立一个数组把1亿个数装起来,然后用for循环遍历这个数组,找出最大的1万个数来。原因很简单,如果要找最大的那个数,就是这样解决的;而找最大的一万个数,只是重复一万遍。这个解法类似于选择排序,一次将一个正确解放在合适的位置,重复一万次,所以时间复杂度为O(n *m),如果你
《算法导论》学习之关于如何利用排序算法,从1亿个数中,选出最大(小)的100个数
首先声明:本文内容是参考别人的博客,链接为:http://blog.csdn.net/beiyeqingteng/article/details/7534489 前言: 刚刚在CSDN上看到一个网友利用最小堆实现 “ 获取一亿数据获取前100个最大值” 。原帖请看:http://blog.csdn.net/yjflinchong/article/details/7533972。
10亿个数中找出最大的10000个数(top K问题)
前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。 先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然...
[原创]从1亿个数据中找出前100个最大值
从一亿个数据中找出前100个最大值 方法一: &amp;gt; 新建一100个红黑树节点,将输入前100个保存进去,然后全部插入红黑树T &amp;gt; 遍历剩下的所有输入,对每一个输入值,如果值大于红黑树中最小值,则删除最小值节点,然后修改被删除节点的值为当前输入,然后插入红黑树。 复杂度为n*lg(m), n为输入数据条数,m为输出数据条数 方法二:将红黑树替换成最小堆,每插入一条数据,只需要运行...
(算法)从10000个数中找出最大的10个
从10000个整数中找出最大的10个,最好的算法是什么? 算法一:冒泡排序法   千里之行,始于足下。我们先不说最好,甚至不说好。我们只问,如何“从10000个整数中找出最大的10个”?我最先想到的是用冒泡排序的办法:我们从头到尾走10趟,自然会把最大的10个数找到。方法简单,就不再这里写代码了。这个算法的复杂度是10N(N=10000)。 算法二:   有没有更好一点的算
从一亿个数中找出最大的一万个数或最小的一万个数
1 从一亿个数中找出最大的一万个数:(前10000个元素构建最小堆,后续元素与根节点比较,大于放进去,小于或等于不处理) 用前一万个数初始化一个固定大小为10000的最小堆,这时根节点是这10000个数里最小的一个。 把后续的数依次与最小堆的根节点比较,如果大于则放进最小堆(这个操作同时会弹出一个元素并改变根节点),小于等于不做处理。 这个算法的复杂度几乎接近于O(n) 2 从一亿
算法2— 一亿数据获取前100个最大值
刚刚在CSDN上看到一个网友利用最小堆实现 “ 获取一亿数据获取前100个最大值” 。然后自己利用quicksort的原理也写了一个程序来解决那个问题。通过测试,基于quicksort原理的方法平均运行时间是1.264秒,基于最小堆方法的平均运行时间是0.288秒 (网友写的程序运行时间比我的大很多,0.288秒这个程序是我自己写的,如果测试网友写的基于minHeap的方法,运行时间是2.501秒
10亿个数中找出最大的10000个数之top K问题
    方法一、先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlogm),算法的时间复杂度为O(nmlogm)(n为10亿,m为10000)。    方法二(优化的方法):可以把所有10亿个数据分组存放,比如分别放在100...
百度面试题:在100w个数中找最大的前100个数
在100w个数中找最大的前100个数 答案在文章评论部分,请注意查看:) 原文网址:http://hi.baidu.com/mianshiti/blog/item/37652f27a3ac4320d5074252.html -----------------
10亿数中找出最大1000个数的算法C实现(简化版)
此处主要采用堆排序来实现。 typedef int ElementType; typedef struct { ElementType *r; int length; }SqList; #define N 20 #define M 10 void Heap
100亿个数字中找出最大的10个
100亿个数字找出最大的10个 1、首先一点,对于海量数据处理,思路基本上是:必须分块处理,然后再合并起来。 2、对于每一块必须找出10个最大的数,因为第一块中10个最大数中的最小的,可能比第二块中10最大数中的最大的还要大。 3、分块处理,再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器,每个服务器又有很多的CPU,因此,100亿个数分成100块,
100亿个数中找出最大的前K个数(海量TopK问题)
对于这个问题,可以有以下思考: 给了多少内存存储这100亿个数据? 先思考:堆排序效率是nlogn,再思考:可以将这些数据切成等份,再从每一份中找出最大前k个数据,但是效率不高。那如果利用堆的性质呢? 小堆堆顶元素最小,先将前k个数建成小堆,那么堆顶元素就是最小的,k+1的数依次与堆顶元素进行比较,如果大于,则K+1与堆顶元素交换,依次循环直至所有数据全部比较完,那么这个堆里存放的是最大的前...
100000个数找出最小或最大的10个
大体思路: 首先一点,对于海量数据处理,思路基本上是确定的,必须分块处理,然后再合并起来。 对于每一块必须找出10个最大的数,因为第一块中10个最大数中的最小的,可能比第二块中10最大数中的最大的还要大。 分块处理,再合并。也就是Google MapReduce 的基本思想。Google有很多的服务器,每个服务器又有很多的CPU,因此,100亿个数分成100块,每个服务器处理一块,1亿个数分成...
10亿个数中找出最大的10000个数(top K问题)
前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。建堆时间复杂度是O(mlo
一亿数据获取最大值的前100位
两种思路: 1. 根据快速排序划分的思想  a. 假设数组为 array[N] (N = 1 亿),首先利用quicksort的原理把array分成两个部分,左边部分比 array[N - 1] (array中的最后一个值,即pivot) 大, 右边部分比pivot 小。然后,可以得到 array[array.length - 1] (即 pivot) 在整个数组中的位置,假设是 k.
从1亿个数字中取出最大的100个数字- 位图排序(空间换时间)
/* *一个排序算法题:从1亿个数字中取出最大的100个 *装逼宝典:位图公式 bitmap[arr[i]]=1; 将传统数组转换为位图数组就完成了排序!!! * *什么是位图?答:构建公式:bitmap[arr[i]]=1; 其中arr是我们的传统数组,bitmap是位图数组。 *位图长度多少?答:bitmap.length=arr[i].maxValue; 因为位图数组基于传
从100亿个整数中找出最大/最小的1000个整数
一句话总结:内存无法装下,用比较速度最快的数据结构。 先找最大的1000个整数 1、内存无法装下:先取出1001个整数,构建一个最小堆,堆顶永远是最小的整数。 2、比较:从剩余的整数中一次取出一个,跟最小堆堆顶相比,如果比堆顶小,就pass掉,接着取;如果比最小堆堆顶大,那么将之替换掉堆顶,然后调整最小堆 3、结果:100亿个整数全部操作完后,抛开堆顶,剩下的1000个就是最大的1000个
5亿个数找中位数
找中位数最容易想到的方法就是,先对序列进行排序,取中位数,然而5亿个数要想全部读入内存需要将近2GB空间。 一种想法是采用外部排序的方法,在排序的过程中记录数据个数,找到中位数。首先采用hash() % 100,把数据分到100个文件中,然后对每个文件分别在内存中进行快速排序,再将100个小文件进行合并,并在合并过程中寻找中位数,时间复杂度是O(nlogn)   另外一种方法是,
从1亿个数里面找出前100个最大的
从1亿个数里面找出前100个最大的 这个题目应该是一些大公司面试题中经常被问到的,这里我给出一种做法,至于面试官满不满意我就不知道了。我们知道,这种找出前多少个最大或者最小的最适合用堆排序(对堆排序不熟悉的读者可以参考为的这篇博客:堆排序)。但是如果我们用1亿个数去建堆并调整,当然时间复杂度是不允许的。题目中要求前100个大的,那么我们就只用100...
从一亿个数中找出最大的100个 或者n个
从一亿个数中找出最大的100个 或者n个 用了个堆
java一亿数字取前100个(3秒钟获取)
java一亿数字取前100个(3秒钟获取) 速度非常快。 发出来给大家分享
100亿个整数,找出中位数
100亿个整数,内存足够,如何找到中位数?内存不足,如何找到中位数? (1)当内存足够时:采用快排,找到第n大的数。 • 随机选取一个数,将比它小的元素放在它左边,比它大的元素放在右边 • 如果它恰好在中位数的位置,那么它就是中位数,直接返回 • 如果小于它的数超过一半,那么中位数一定在左半边,递归到左边处理(还是第几大) • 否则中位数一定在右半边,根据左半边的元素个数
10.百度最新面试题:现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来。
10.百度最新面试题:现在有1千万个随机数,随机数的范围在1到1亿之间。现在要求写出一种算法,将1到1亿之间没有在随机数中的数求出来。 (编程珠玑上有此类似的一题,如果有足够的内存的话可以用位图法,即开一个1亿位的bitset,内存为100m/8== 12.5m, 然后如果一个数有出现,对应的bitset上标记为1,最后统计bitset上为0的即可。) 转 http://blog.cs
100亿个数中找出最大的前K个数(海量数据topK问题)
分析:海量数据topK问题,在我们日常生活中应用非常广泛,比如微信的计步软件,它就是topK问题,统计出前K名,然后进行排序。那如何解决这个问题呢?我们用堆可以很好的解决这个问题。我们先用前K个数建立一个大堆/小堆(找最大前K个数用小堆,找最小前K个数用大堆,因为:如果找最大前K个数,我们建立一个大堆的话,我们需要用第N-K-1个数与堆顶元素比较,如果它比堆顶元素小我们就要舍弃它,但如果它比堆顶元...
海量数据处理 - 10亿个数中找出最大的10000个数(top K问题)
前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。         先拿10000个数建堆,然后一次添加剩余元素,如果大于堆顶的数(10000中最小的),将这个数替换堆顶,并调整结构使之仍然是一个最小堆,这样,遍历完后,堆中的10000个数就是所需的最大的10000个。建堆
从10000000个元素里面找出最大的前100个
           如题,从最大的10000000个元素里面找出最大的前100个,下面是我的代码实现:           import java.util.Comparator; import java.util.PriorityQueue; import java.util.Random; import java.util.logging.Logger; public ...
10亿数据中取最大的100个数据
思路1:根据快速排序划分的思想 (1)递归对所有数据分成[a,b)b(b,d]两个区间,(b,d]区间内的数都是大于[a,b)区间内的数 (2)对(b,d]重复(1)操作,直到最右边的区间个数小于100个。注意[a,b)区间不用划分 (3)返回上一个区间,并返回此区间的数字数目。接着方法仍然是对上一区间的左边进行划分,分为[a2,b2)b2(b2,d2]两个区间,取(b2,d2]区间。如果
经典算法应用之七----10亿数据中取最大的100个数据
给出三种思路,仅供参考。。 1.思路一:根据快速排序划分的思想,每次分割之后只考虑比轴大的一部分,知道比轴大的一部分在比100多的时候,采用传统排序算法排序,取前100个。 step1:递归对所有数据分成[a,b),(b,d]两个区间,(b,d]区间内的数都是大于[a,b)区间内的数 step2:对(b,d]重复step1操作,直到最右边的区间个数小于100个。注意[a,b)
答复: 一道腾讯面试题:从大量数字中取出 top 100
从1亿个数字中取出最大的100个 JVM需要调到-Xmx1024M,以免溢出 [code=&quot;java&quot;] public class findValue { public static void main(String[] args){ int max = 10000*10000; int length=100; int ints[] = new in...
给定1亿int,找出最大的100个
给定1亿个数,找出 最大的 100个 1. 用一个长度是 101 的数组,建立 小顶堆(0号元素不用,主要是为了使用堆的性质:父结点i,则,左右结点是 2i 和 2i+1) 2. 用堆顶 和 每个 取得的数 进行比较。(a. 堆顶 >= 取得的数,则,忽略 取得的数 b. 否则,把堆顶 替换为 取得的数) 3. 新得到的堆, 堆顶 的左右子树 都是 完美堆。需要调整 堆顶(调整算法 就是 构
在一亿个数中查找最大的k个数(k << 1,000,000,000)
在一亿个整数中查找最大(小)的k个数(k         之前跟一同事说起互联网公司的面试题,他说一般思路是先排序,然后再处理数据肯定没错。是不是这样的呢?对于这个问题,我们想想如下的几个方法:         1.使用大多数情况下最快的排序方法—快速排序来解决可以吗?思路是将一亿个整数放到一个数组中,然后使用快速排序方法把最大的k个数放到数组的前k个空间里。但是,这个问题没有说(1)要排好
从10万个数中找10个最大的数
对于这种题目,最普通的想法是先对这10万个数进行排序,然后再选取数组中前10个数,即为最后的答案,排序算法的时间复杂度不下于O(N lgN)。最好的方法是建立一个最小堆。 算法描述: 我们首先取10万个元素中的前10个元素来建立由10个元素组成的最小堆。这样堆顶元素便是当前已知元素的第10大的数;然后依次读取剩下的99990个元素,若读取的元素比堆顶元素大,则将堆顶元素和当前元素替换,并自堆顶至
文章热词 设计制作学习 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 python教程100 java3个班级4个学生