首页 > 代码库 > 编程算法 - 最小的k个数 红黑树 代码(C++)
编程算法 - 最小的k个数 红黑树 代码(C++)
最小的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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。