在无序数组中寻找最小的k个数
/*在数组中寻找最小的k个数
例如，输入：4,5,1,6,2,7,3,8 这8个数字，
输出最小的4个数是：1,2,3,4
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
#include<set>
#include<functional>
using namespace std;
class Solution
{
public:
void GetLeastnumbers(const vector<int> &data, multiset<int, greater<int>> &leastNumbers, int k)
{
leastNumbers.clear();
if(k<1 || data.size()<k)
return;
vector<int> ::const_iterator iter=data.cbegin();
for( ; iter!=data.cend(); ++iter)
{
if(leastNumbers.size()<k)
leastNumbers.insert(*iter);
else
{
multiset<int, greater<int>>::iterator interGreatest=leastNumbers.begin();
if(*iter < *(leastNumbers.begin()))
{
leastNumbers.erase(interGreatest);
leastNumbers.insert(*iter);
}
}
}
}
};
int main(void)
{
int input[]={4,5,1,6,2,7,3,8};
vector<int> data(begin(input),end(input));
int k=0;
cin>>k;
multiset<int, greater<int>> leastNumbers;//辅助内存空间
class Solution object;
object.GetLeastnumbers(data,leastNumbers,k);
for(auto mem:leastNumbers)
cout<<mem<<",";
cout<<endl;
system("pause");
return 0;
}
/*在数组中寻找最小的k个数
例如，输入：4,5,1,6,2,7,3,8 这8个数字，
输出最小的4个数是：1,2,3,4
*/
#include<iostream>
#include<vector>
#include<algorithm>
#include<numeric>
using namespace std;
class Solution
{
public:
void GetLeastnumbers(int input[], int n, vector<int> &res,int k)
{
if(input==nullptr || k>n || n<=0 || k<=0)
return;
int start=0;
int end=n-1;
int index=partion(input,n,start,end);
while(index!=k-1)
{
if(index>k-1)
{
end=index-1;
index=partion(input,n,start,end);
}
else
{
start=index+1;
index=partion(input,n,start,end);
}
}
for(int i=0; i<k; ++i)
res[i]=input[i];
}
public:
int partion(int input[], int n, int start, int end)
{
if(input==nullptr || n<1)
return -1;
int i=start;
int j=end;
while(i<j)
{
while(i<j && input[i]<=input[j])
--j;
if(i<j)
{
swap(input[i],input[j]);
++i;
}
while(i<j && input[i]<=input[j])
++i;
if(i<j)
{
swap(input[i],input[j]);
--j;
}
}
return i;
}
};
int main(void)
{
int input[]={4,5,1,6,2,7,3,8};
int n=sizeof(input)/sizeof(input[0]);
int k=0;
cin>>k;
vector<int> res(k);
class Solution object;
object.GetLeastnumbers(input,n,res,k);
for(auto mem:res)
cout<<mem<<",";
cout<<endl;
system("pause");
return 0;
}