输入n个数,找出其中最小的k个数。例如输入4,5,1,6,2,7,3,8 这8个数,则最小的4个数是1,2,3,4.
解法一:O(n)的算法,只有当我们可以修改输入数组时可用
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 }
解法二:O(nlogk)的算法,特别适合处理海量数据
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 }
原文:http://www.cnblogs.com/csxcode/p/3720994.html