在10000000个数(int)中求最小的10000个数

bb2bb

原帖由 converse 于 2007-8-23 01:52 发表


.....

还是坚持要用你的MAP？

ypxing

不是求第k个,而是求前k个

原帖由 Orpherus 于 2007-8-23 02:08 发表
我有个想法
快排的时候pation把目标分为两个区间
左区间小于右区间

k=10000
设左区间有p个数
若pk 则递归的对左区间继续分区  
若p==k 结束

jigloo

得得， 最烦你们这些孔已己了。动不动就说别人错的。
我只是帮楼上美化了一下程序，就有人迫不及待的跳出来了。

partial_sort和nth_element的两种写法不需要别人来考我一考吧？

to楼上: 用[code][/code]把代码包起来既可。

[[i] 本帖最后由 jigloo 于 2007-8-23 10:24 编辑 [/i]]

OVERAGAIN

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. /*十个数取最小的三个*/
   
5. int  main(void)
   
6. {
   
7.         int iArray[10+1] = { 7,10,5,3,4,3,6,-1,8,1 };
   
8.         int iTemp = 0;
   
9.         int i = 0;
   
10.         int ii = 0;
    
11.         for( i = 3;i < 10;i++ )
    
12.         {
    
13.                 for( ii = 0;ii < 3;ii++ )
    
14.                 {
    
15.                         if( iArray[i] < iArray[ii] )
    
16.                         {
    
17.                                 iTemp = iArray[i];
    
18.                                 iArray[i] = iArray[ii];
    
19.                                 iArray[ii] = iTemp;
    
20.                         }                       
    
21.                 }
    
22.         }
    
23.         printf("%d\n",iArray[0]);
    
24.         printf("%d\n",iArray[1]);
    
25.         printf("%d\n",iArray[2]);
    
26.         return 0;
    
27. }

复制代码

醉卧水云间

原帖由 zhkl125 于 2007-8-23 10:16 发表
只是多做了点事情而已，不能算错

楼主要速度，你多排序就没速度了。

anhongkui

分治法　应该可以

apsong

原帖由 bb2bb 于 2007-8-23 10:13 发表
用partial_sort就是错的，前10000个不需要排序。

哦~又看了下，发现nth_element不仅找到排第N的元素，还让<N和>N的元素分别在N两边。对LZ的要求来说确实就最合适了。

醉卧水云间

原帖由 apsong 于 2007-8-23 10:59 发表

哦~又看了下，发现nth_element不仅找到排第N的元素，还让N的元素分别在N两边。对LZ的要求来说确实就最合适了。

nth_element是标准用法，问题是楼主的算法能否快过这个，这是我比较感兴趣的。