编程算法

最小的k个数 红黑树 代码(C++)

本文地址： http://blog.csdn.net/caroline_wendy

题目: 输入n个整数, 找出当中的最小k个数.

使用红黑树(multiset), 每次替换最大的值, 依次迭代.

时间复杂度: O(nlogk).

代码:

/*
 * main.cpp
 *
 *  Created on: 2014年6月29日
 *      Author: wang
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <set>

using namespace std;

void GetLeastNumbers (const vector<int>& data,
		multiset<int, greater<int> >& leastNumbers,
		std::size_t k)
{
	leastNumbers.clear();

	if (k < 1 || data.size() < k)
		return;

	for (vector<int>::const_iterator iter = data.begin();
			iter != data.end(); ++iter)
	{
		if (leastNumbers.size() < k) {
			leastNumbers.insert(*iter);
		} else {
			multiset<int, greater<int> >::iterator iterGreatest = leastNumbers.begin();

			if (*iter < *iterGreatest) {
				leastNumbers.erase(iterGreatest);
				leastNumbers.insert(*iter);
			}
		}
	}
}

int main(void)
{
    vector<int> input =  {4, 5, 1, 6, 2, 7, 3, 8};
    multiset<int, greater<int> > output;
    GetLeastNumbers (input, output, 4);
    std::copy(output.begin(), output.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
    return 0;
}

输出:

4 3 2 1