编程算法 - 最小的k个数红黑树代码(C++)-白红宇

编程算法 - 最小的k个数红黑树代码(C++)

阅读量：5117 次

发布时间：2019-06-13

本文共 1117 字，大约阅读时间需要 3 分钟。

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

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

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

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

时间复杂度: O(nlogk).

代码:

/* * main.cpp * *  Created on: 2014年6月29日 *      Author: wang */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;void GetLeastNumbers (const vector
          
           & data, multiset

>& leastNumbers, std::size_t k){ leastNumbers.clear(); if (k < 1 || data.size() < k) return; for (vector

::const_iterator iter = data.begin(); iter != data.end(); ++iter) { if (leastNumbers.size() < k) { leastNumbers.insert(*iter); } else { multiset

>::iterator iterGreatest = leastNumbers.begin(); if (*iter < *iterGreatest) { leastNumbers.erase(iterGreatest); leastNumbers.insert(*iter); } } }}int main(void){ vector

input = {4, 5, 1, 6, 2, 7, 3, 8}; multiset

> output; GetLeastNumbers (input, output, 4); std::copy(output.begin(), output.end(), std::ostream_iterator

(std::cout, " ")); std::cout << std::endl; return 0;}

输出:

4 3 2 1

转载于:https://www.cnblogs.com/mengfanrong/p/4014298.html

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

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