题目描述：输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

题目解析：首先想到的就是插入法，。改进一下就是前面一直保持7个有序数字。遍历剩下数组，元素若小于最大值就交换。用C++的set来解决代码就简洁多了，删除插入都是logk。

 

代码如下：

1 class Solution { 2 public: 3     vector
     
       GetLeastNumbers_Solution(vector
      
        input, int k) { 4         set
       
         kset; 5         if(k <= 0 || input.size() < unsigned(k)) return vector
        
         (0); 6         vector
         
          ::iterator iter = input.begin(), iend = input.end(); 7         while(k--) { 8             kset.insert(*iter++); 9         }10         11         while(iter != iend) {12             if(*iter < *kset.rbegin()) {13                 kset.erase(*kset.rbegin());14                 kset.insert(*iter++);15             }16             else ++iter;17         }18         19         vector
          
            ans(kset.begin(), kset.end());20 return ans;21 }22 };
          
         
        
       
      
     

拓展：quick select