题目要求：
输入n个整数，输出其中最小的k个。
例如：输入1,2,3,4,5,6,7,8这8个数字，则最小的4个数字为1,2,3,4。
参考资料：剑指offer第30题。
题目分析：
解法一：
用快排的思想，但是最小的k个数不用排序，时间复杂度O(n).
优点：时间复杂度好，缺点：会修改原整数数组顺序。
解法二：
创建一个大小为k的最大堆，遍历一遍数组，同时不断修改最大堆。时间复杂度O(nlogk).
优点：不会修改原数组，适用于海量数据。缺点：比解法一时间复杂度高。
其他解法：
1.快排，取前k个数，时间复杂度O(nlogn).
2.遍历k次，时间复杂度O(k*n).
3.位图排序，取前k个数，时间复杂度O(n).会占用额外的空间.
解法一代码：
#include <iostream>
#include <stdlib.h>
using namespace std; inline int my_rand(int low, int high)
{
int size = high - low + ;
return low + rand() % size;
}
int partition(int a[], int low, int high)
{
int val = a[low]; while(low<high)
{
while( (low<high) && (a[high]>=val) )
high--; a[low] = a[high];
while( (low<high) && (a[low] <= val) )
low++;
a[high] = a[low];
}
a[low] = val;
return low;
}
void swap(int *a,int i,int j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
bool rand_select(int array[], int left, int right, int k)
{
//第k 小元素，实际上应该在数组中下标为 k-1
if (k- > right || k- < left)
return false ; if(left<right)
{
//随机从数组中选取枢纽元元素
int index = my_rand(left, right);
swap(array,index,left); int pos = partition(array , left, right);
if(pos == k-)
return true ;
else if (pos > k-)
return rand_select(array , left, pos-, k);
else return rand_select(array, pos+, right, k);
}
else
return true ;
}
int main()
{
int array1[] = {, , , , , , , , , }; int numOfArray = sizeof (array1) / sizeof( int);
for(int i=; i<numOfArray; i++)
cout << array1[i] << " ";
cout << endl; int K = ;
bool flag = rand_select(array1, , numOfArray-, K); if(flag)
{
cout << "最小的" << K << "个数为：";
for(int i=; i<K; i++)
cout << array1[i] << " ";
cout << endl;
}
return ;
}
解法二代码：
//从头实现一个最大堆需要一定的代码，可以采用c++中的红黑树来实现。
//其中set和multiset都是基于红黑树实现的，后者可以支持数组中有重复
#include <iostream>
#include <set>
#include <vector> using namespace std; typedef multiset<int,greater<int>> intSet;
typedef multiset<int,greater<int>>::iterator setIterator; void getLeastNumbers(const vector<int> &data,intSet &leastNumbers,int k); int main(void)
{
int a[] = {,,,,,,,};
const vector<int> data(a,a+);//8不是7 intSet leastNumbers;
int k = ; getLeastNumbers(data,leastNumbers,k); cout << "最小的" << k << "个数为:";
setIterator iter = leastNumbers.begin();
for(;iter!=leastNumbers.end();++iter)
cout << *iter << " ";
cout << endl;
return ;
}
void getLeastNumbers(const vector<int> &data,intSet &leastNumbers,int k)
{
leastNumbers.clear(); if(k< || k>data.size())
return ; vector<int>::const_iterator iter = data.begin();
for(;iter != data.end();++iter)
{
if(leastNumbers.size() < k)
leastNumbers.insert(*iter);
else
{
setIterator iterGreatest = leastNumbers.begin();
if(*iter < *iterGreatest)
{
leastNumbers.erase(*iterGreatest);
leastNumbers.insert(*iter);
}
}
}
}