程序员面试100题(算法)之输入n个整数，输出其中最小的k个

[cpp] view plaincopy

1. // Test3.cpp : 定义控制台应用程序的入口点。   
2. // 程序员面试100题(算法)之输入n个整数，输出其中最小的k个   
3.   
4. #include "stdafx.h"   
5. #include<iostream>   
6. #include<vector>   
7. #include<set>   
8.   
9. using namespace std;  
10.   
11. void findKLeastNumbers(multiset< int, greater<int> > &container, vector<int> &vec, int k)  
12. {  
13.     container.clear();  
14.   
15.     if(vec.size() < k || k <= 0 || vec.empty())  
16.         cout << "Please check your parameters" << endl;  
17.   
18.     vector<int>::iterator iter = vec.begin();  
19.   
20.     for(; iter != vec.end(); iter++)  
21.     {  
22.         if(container.size() < k)  
23.         {  
24.             container.insert(*iter);  
25.         }  
26.         else  
27.         {  
28.             multiset< int, greater<int> >::iterator cIter = container.begin();  
29.   
30.             if(*iter < *cIter)  
31.             {  
32.                 container.erase(cIter);  
33.                 container.insert(*iter);  
34.             }  
35.         }  
36.     }  
37. }  
38.   
39. void createVector(vector<int> &vec)  
40. {  
41.     int num;  
42.   
43.     cout << "Please input the numbers(65536 means ending)" <<endl;  
44.     while(cin >> num)  
45.     {  
46.         if(65536 == num)  
47.             break;  
48.         vec.push_back(num);  
49.     }  
50. }  
51.   
52. void printMultiset(multiset< int, greater<int> > numbersSet)  
53. {  
54.     multiset< int, greater<int> >::iterator iter = numbersSet.begin();  
55.   
56.     for(; iter != numbersSet.end(); iter++)  
57.     {  
58.         cout << *iter << "\t";  
59.     }  
60.   
61.     cout << endl;  
62. }  
63.   
64. int _tmain(int argc, _TCHAR* argv[])  
65. {  
66.     int k =0;  
67.     vector<int> vec;  
68.     multiset< int, greater<int> > container;  
69.   
70.     createVector(vec);  
71.     cout << vec.size() << endl;  
72.   
73.     cout << "Please input the k:" <<endl;  
74.     cin >> k;  
75.     findKLeastNumbers(container, vec, k);  
76.     cout << "The least k numbers are:" <<endl;  
77.     printMultiset(container);  
78.   
79.     return 0;  
80. }