这是比较常见的一个面试题了.
看到一篇比较好的文章,留下网址和阅读笔记.
地址:http://blog.csdn.net/shadowkiss/archive/2008/12/19/3557873.aspx
其中针对问题,算法上进行不断地优化,是一大亮点,其优化过程包括:
不假思索
stupid,[选择排序]每次找出余下数组中最大的,重复1万次.
稍作思考
快排后,提取前一万个.
深入思考
最先抽取头部1万个整数作为resultArr(排序后,找出其中最小数),之后遍历余下数据BigArray,发现有比最小数据大的,覆盖之,并重新找出最小元素,如此反复,直至bigArray遍历完全.
ps.最小元素的查找是优化重点,注意缩减查找范围.下面的优化都集中在这里.
深思熟虑
最小元素的查找在一定范围内进行,先按左大右下排列初选出的ResultArr数组,第一次最小元素指向ResultArr的尾端,每替换一次,后移一位,查找范围加一.
苦思冥想
每次的替换操作会导致resultArr无序,在替换一定次数后,重新整理resultArr,用归并使之有序.
殚思极虑
替换操作 只会导致尾部局部数据无序,只需先排序该部分数据,之后进行有序数据的合并.
ps.以上都是我自己阅读后的缩写,留待日后复习之用,很难想象不认真阅读原文能看出任何体会.
ps2.当然了,我自己也有一个思路完全不同的解法,主要思想是以快排为原型,但稍作修改.
每次按快排寻找到支点后(按从小到大),对支点左右的element个数进行判断,如若右边个数小于需要找出的元素个数,则只对支点左边的数组递归调用快排.如此反复,直至右边元素达到指定个数.至于实际的代码实现,待完成
分享到:
相关推荐
从一亿个数中找出最大的100个 或者n个 用了个堆从一亿个数中找出最大的100个 或者n个 用了个堆
C语言程序设计-找出一批正整数中的最大的偶数;
给定程序中,函数fun的功能是:在任意给定的9个正整数中找出按升序排列是处于中间的数,将原数据序列中比该中间数小的数用该中间数替换,位置不变,在主函数中输出处理后的数据序列,并将中间数作为函数值返回。...
数组a中已存有互不相同的10个整数从键盘输入一个整数,找出与该值相同的数组元素下标。 (如果没找到,输出“没找到”).c
求一个含有8个整数的数组中前3个最大值对应的下标,将对应的下标置1其它为0,然后将所得的八位二进制数转换成一个十进制数。
C语言程序设计-找出一个大于给定整数且紧随这个整数的素数,并作为函数值返回;
从输入的一批正整数中求出最大值、最小值和平均值,输入0结束数据的输入。C语言程序
找出一个整数是哪些个连续整数的和(例如:15=1+2+3+4+5,15=4+5+6,15=7+8)
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;本.cC语言程序设计-
C语言程序设计-从键盘为一维整型数组输入10个整数,调用fun函数找出其中最小的数,并在main函数中输出;请编写fun函数;.c
设有n个正整数,将他们连接成一排,组成一个最大的多位整数。 如:n=3时,3个整数13,312,343,连成的最大整数为34331213。 如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613。 输入描述: 有多组测试样例,每组...
从键盘读入8个整数存入数组a中并输出这8个数据。 ⑴求出这8个数据的和、最大值、最小值及平均值。 ⑵求这8个数据的正数之和、负数之和(或正数与负数的个数); ⑶求这8个数据的奇数之和、偶数之和(或奇数与偶数的...
主要介绍了C++通过自定义函数找出一个整数数组中第二大数的方法,涉及C++针对数组的遍历操作相关技巧,需要的朋友可以参考下
按从大到小顺序排序输出合并后的整数集(去掉在两组整数中都出现的整数,以一个空格分隔各个整数)。 【样例输入】 5 1 4 32 8 7 9 -6 5 2 87 10 1 【样例输出】 87 32 10 9 8 7 4 2 -6 【样例说明】 第一...
本题要求编写程序,找出给定的n个数中的最大值及其对应的最小下标(下标从0开始)。 输入格式: 输入在第一行中给出一个正整数n(1≤10)。第二行输入n个整数,用空格分开。 输出格式: 在一行中输出最大值及最大值...
找出一组数(N 个整数,N,未排序)的中位数。
从键盘输入两个正整数,求这两个正整数的最小公倍数和最大公约数,并输出。 输入 输入包括一行。 两个以空格分开的正整数。 输出 两个整数的最小公倍数和最大公约数。 样例输入 6 8 样例输出 24 2
任意给定 n 个整数,求这 n 个整数序列的和、最小值、最大值 输入描述 输入一个整数n,代表接下来输入整数个数,n,接着输入n个整数,整数用int表示即可。 输出描述 输出整数序列的和、最小值、最大值。用空格隔开...
课程的随堂作业,C语言的,用dev就能运行,萌新代码,勿喷,仅仅帮助不想写作业的朋友方便一下,反正老师也不会仔细检查的