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

题目

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

思路

最直接的肯定是sort+前k位输出（貌似这样在力扣上还省时一点）

研究了一下书上的方法，用一个STL容器完成，维持一个容量为k的堆，保证这个堆中的数据都是最小的。

代码

class Solution {public:    vector
   
     getLeastNumbers(vector
    
     & arr, int k) {        multiset
     
      
       > minset;                for(int i = 0;i < arr.size();i++){            if(minset.size() < k){                minset.insert(arr[i]);            }else{                multiset
       
        
         >::iterator ite; ite = minset.begin(); if(arr[i] < *ite){ minset.erase(ite); minset.insert(arr[i]); } } } vector
         
           vec; vec.assign(minset.begin(), minset.end()); return vec; }};
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105765676 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！