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

// Test3.cpp : 定义控制台应用程序的入口点。
// 程序员面试100题(算法)之输入n个整数，输出其中最小的k个

#include "stdafx.h"
#include<iostream>
#include<vector>
#include<set>

using namespace std;

void findKLeastNumbers(multiset< int, greater<int> > &container, vector<int> &vec, int k)
{
	container.clear();

	if(vec.size() < k || k <= 0 || vec.empty())
		cout << "Please check your parameters" << endl;

	vector<int>::iterator iter = vec.begin();

	for(; iter != vec.end(); iter++)
	{
		if(container.size() < k)
		{
			container.insert(*iter);
		}
		else
		{
			multiset< int, greater<int> >::iterator cIter = container.begin();

			if(*iter < *cIter)
			{
				container.erase(cIter);
				container.insert(*iter);
			}
		}
	}
}

void createVector(vector<int> &vec)
{
	int num;

	cout << "Please input the numbers(65536 means ending)" <<endl;
	while(cin >> num)
	{
		if(65536 == num)
			break;
		vec.push_back(num);
	}
}

void printMultiset(multiset< int, greater<int> > numbersSet)
{
	multiset< int, greater<int> >::iterator iter = numbersSet.begin();

	for(; iter != numbersSet.end(); iter++)
	{
		cout << *iter << "\t";
	}

	cout << endl;
}

int _tmain(int argc, _TCHAR* argv[])
{
	int k =0;
	vector<int> vec;
	multiset< int, greater<int> > container;

	createVector(vec);
	cout << vec.size() << endl;

	cout << "Please input the k:" <<endl;
	cin >> k;
	findKLeastNumbers(container, vec, k);
	cout << "The least k numbers are:" <<endl;
	printMultiset(container);

	return 0;
}