首页 > 代码库 > 最小的K个数

最小的K个数

2024-07-03 23:54:57   224人阅读

输入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 }

 


联系
我们