最小的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