`
king_tt
  • 浏览: 2083875 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

算法设计:从一个很大很大的数组里找前N个最大数的思路之一

 
阅读更多
这里先讲一种类似于快速排序的方法。注意题目要求,不要求完全排序,只要求最快解决问题!这个题是我面试NI公司时,对方问我的。原话是从1亿个数据里,找出前一百个最大的。

首先看源码吧:

void main(int a[], int start, int end, int N)//从数组a里,找出前N个最大的。如果是a[100],则start = 0, end = 99.注意这个索 引问题

{
int mid = (start + end)/2;

int i = start, j = end;

while(i<j)

{
while(i<j && a[i]<=a[mid])

i++;

while(i<j && a[j]>=a[mid])

j--;

swap(a[i], a[j]);

}
/*注意这个while出来之后,i一定是等于j的,且从i 到 end是较大的那一端*/

if(end-i+1 == N)

return;

if(end - i+1 > N)

findMaxN(a, i, end, N);

else

findMaxN(a, start, i, N - (end -i +1));

}
再来详细说说思路,如果您看懂了快速排序对此一定不会陌生。首先拿a[mid] 做基准值,然后让i, j从两端开始遍历,如果索引小的那一端数据小于基准值a[mid], 就往前遍历,如果 左边的大于了a[mid], while循环会跳出,记住这时的a[i] 是大于a[mid],

然后类似的思路,从j那一端遍历,当右边的数据a[j ] 小于基准值a[mid],则小while循环会跳出。然后会运行swap()这个函数,将两个值进行交换 。 这样最外面的while循环出来之后,i一定是等于j的,注意这里i 和j不一定等于当前域中的mid。而且从i到end都是较大的,然后看看较大的那一端的数据有多少个,然后进行遍历。

如果已经等于要找的N个,则跳出函数。如果大于N,则要从i到end为区间内接着找;如果小于N,比如说要找前50个最大的,结果end-i+1才等于20,也就是从i到end有20个较大的数,这就需要从 start(第一次时,可以认为是0)到i 区间内再找50-20 = 30个最大的。

至于swap的函数,利用引用实现如下:

void swap(int &a, int &b)

{

int temp = a;

a = b;

b= temp;}

最后说说,如果这个函数执行完毕了,我怎么访问找到的最大的N个数呢? 很简单,假设数组长度为n, 从a[n-1], a[n-2]。。。顺序取N个数,就是找到的最大的前N个数据了!这个算法的最大情况时间复杂度是o(n的平方),最好情况是o(n), 平坦下来也是o(n).

等我空我介绍第二种思路,上面代码是即兴写的,源码我一会上传。
http://download.csdn.net/detail/yanzi1225627/4684046
分享到:
评论

相关推荐

    求一组数组的两个最大值和两个最小值 分治法

    最终我将一个数组平分成两个小数组,分别求出各数组的两个最大及两个最小值,然后再分别组合4个最大值和四个最小值,最后再比较出大小,得出4个最大值的两个大值,4个最小值数组的两个最小值!不知道是不是分治法,...

    分治算法-求一个数组中的最大值和最小值

    分治思想:将难以直接求解的大问题分解为k个相同的子问题;对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止;

    40个Java算法与数组方面的源码实例集.rar

    40个Java算法与数组方面的源码实例集,这些代码都是比较简单,觉得很实用,有算法、数组、打印出杨辉三角形、求1 2! 3! ... 20!的和、递归方法实例、利用递归方法求阶乘之和、判断大小排序、球从100米高度自由落下,...

    纯数数组去重复算法1千万3秒

    纯数数组去重复1千万3秒1亿30秒,如此类推,不论重复量多少都一样。 纯易代码。 如果成员数比较大,不要点显示,显示会很慢很慢的。只点“加入数组”和“去重复”就可以了。

    java基础。冒泡排序,求数组最大值

    里面有几个很好的javaSe基础题目,比如有javaSe的冒泡排序,求数组的最大值,求数组的最小只,求数组是否对称等等算法实例。

    C#,入门教程与实操,非常具有参考价值的数组算法完整工程源代码,包括:加强版(实数)数组;加强版(整数)数组;加强版(泛型)数组

    第一个数据;最后一个数据;最小数据;最大数据;提取数组数据;提取指定下标数据;加号重载;减号重载;乘号重载;除号重载;排序; 以数组数据为参数的方程式;数组左转;数组右转;左转 num 个数;下标 start 到 ...

    数组中求第K大数的实现方法

    问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们...

    计算大数N的阶乘,N可以任意大,只需修改数组的大小即可。

    该程序小巧精辟,注释详细,很适合初学者上手,本程序克服了计算机字长对计算精度的限制,采用char数组保存计算结果和中间值,从而避开了计算机数值表示范围的限制,实践了大数化小,分而治之的算法精髓。

    上海电机学院C语言实训答案

    输入一个正整数n (1&lt;n),再输入n 个整数,将最小值与第一个数交换,最大值与最后一个数交换,然后输出交换后的n 个数。 (25)抓住肇事者 一辆卡车违反交通规则,撞人后逃跑。现场共有三个目击者,但都没有记住车号...

    PHP判断一个数组是另一个数组子集的方法详解

    今天完成一个算法的过程中,有几个需求模块,其中就有判断$a数组是否是$b数组的子集,可能最近我写c比较多,直接就用for循环实现了,但是感觉代码量比较大,不够优雅!在qq群里集思广益了一下,发现很多php提供的...

    寻找两个有序数组的中位数

    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例2: nums1 = [1, 2] nums...

    一组新的多维数组模板类

    extents是一个数组的维度生成器,用起来的很方便,跟boost学的,不过没仔细看它的实现 ,我觉得我的也不错,哈哈 2.访问元素: sa1[0] = 0;; da1[0] = 0;; sa2[0][0] = 0;; da2[0][0] = 0;; sa3[0][0]...

    三峡大学算法设计与分析论文-倍增思想在算法运用与实现

    我们常常会遇到这样的问题:给定一个有序数组a\left[N\right],需要查找出最大的不小于某个数的数字或者查找出最小的大于某个数的数字,通常的朴素做法是从头到尾遍历一遍,那么时间复杂度就是O\left(n\right)。...

    枚举排序的并行算法MPI程序实现

    对该算法的并行化是很简单的,假设对一个长为n的输入序列使用n个处理器进行排序,只需使每个处理器负责完成对其中一个元素的定位,然后将所有的定位信息集中到主进程钟,由主进程负责完成所有元素的最终排位。

    求解旋转数组的最小数字

    这种算法的思想就是遍历这个数组,由于这个数组是两部分有序的数组,因此遍历这个数组时当后一个数字小于前一个数字时,则后一个(即较小)一定为整个数组中最小的数字。 这种算法的思想很简单,但就是时间复杂度...

    php常用算法(doc)

    思路:每一行的第一位和最后一位是1,没有变化,中间是前排一位与左边一排的和,这种算法是用一个二维数组保存,另外有种算法用一维数组也可以实现,一行一行的输出,有兴趣去写着玩下。 11 11 2 11 3 3 11 4 6 4 ...

    Python语言描述连续子数组的最大和

    题目描述 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。...1、第一个不为负数 2、如果前面数的累加值加上当前数后的值会比当前数小,说明累计值对整体和是有害的;如果前面数的累加值加上当前数后的值比当前数

    数据结构与算法.xmind

    递归拆分出两个有序的数组,从mid的位置开始拆分,递归出口:只有一个值的时候就不用拆分了 合并两个有序的数据 分别往两个数组填充已有序的数据 比较两个数组的值谁小,谁小就放到我们的...

    计算机系数据结构与算法设计.pptx

    设有一个电话号码薄,它记录了N个人的名字和其相应的电话号码,假定按如下形式安排: (a1,b1)(a2,b2)…(an,bn) 其中ai,bi(i=1,2…n) 分别表示某人的名字和对应的电话号码要求设计一个算法,当给定任何一个人的...

    算法心得:高效算法的奥秘(原书第2版).[美]Henry S.Warren,Jr(带详细书签).pdf

    3.2 调整到上一个/下一个2的幂 57 3.2.1 向下舍入 58 3.2.2 向上舍入 59 3.3 判断取值范围是否跨越了2的幂边界 59 3.4 习题 61 第4章 算术边界 63 4.1 检测整数边界 63 4.2 通过加减法传播边界 65 4.3 通过...

Global site tag (gtag.js) - Google Analytics