首页 > 其他 > 详细

最小的K个数

时间:2014-05-11 12:57:21      阅读:374      评论:0      收藏:0      [点我收藏+]

输入n个数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8 这8个数,则最小的4个数是1,2,3,4.

解法一:O(n)的算法,只有当我们可以修改输入数组时可用

bubuko.com,布布扣
 1 int Partitoin(int* input, int low, int high)
 2 {
 3     if (input == NULL || low < 0 || high < 0 || low > high)
 4     {
 5         return -1;
 6     }
 7     int temp = input[low];
 8     while(low < high)
 9     {
10         while (high>low && input[high] >= temp)
11         {
12             high--;
13         }
14         input[low] = input[high];
15         while (low<high && input[low] <= temp)
16         {
17             low++ ;
18         }
19         input[high] = input[low];
20     }
21     input[low] = temp ;
22 
23     return low ;
24 }
25 
26 void GetLeastNumbers(int* input , int length, int k)
27 {
28     if (input == NULL || length < 1 || k < 0 || k >length)
29     {
30         return;
31     }
32     int low = 0 ;
33     int high = length - 1 ;
34     int index = Partitoin(input, low, high);
35     while (index != (k - 1))
36     {
37         if (index < (k - 1))
38         {
39             low = index + 1;
40             index = Partitoin(input, low, high);
41         }
42         else
43         {
44             high = index - 1 ;
45             index = Partitoin(input, low, high);
46         }
47     }
48     for (int i = 0 ; i < k ; i++)
49     {
50         cout<<input[i]<<" ";
51     }
52 }
bubuko.com,布布扣

解法二:O(nlogk)的算法,特别适合处理海量数据

bubuko.com,布布扣
 1 typedef  multiset<int , greater<int> > intSet ;
 2 typedef intSet::iterator  setIterator ;
 3 void GetLeastNumbers(vector<int>& data , intSet& leastNumbers, int k)
 4 {
 5     if (k < 1 || data.size() < k)
 6     {
 7         return;
 8     }
 9 
10     vector<int>::iterator ite = data.begin();
11     for (;ite != data.end() ; ite++)
12     {
13         if ( (leastNumbers.size()) < k)
14         {
15             leastNumbers.insert(*ite);
16         }
17         else  
18         {
19             setIterator iterGreatest = leastNumbers.begin() ; 
20             if (*ite < *iterGreatest)
21             {
22                 leastNumbers.erase(iterGreatest);
23                 leastNumbers.insert(*ite);
24             }
25         }
26         
27     }
28 }
bubuko.com,布布扣

 

最小的K个数,布布扣,bubuko.com

最小的K个数

原文:http://www.cnblogs.com/csxcode/p/3720994.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!