题目描述 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。 解题思路：使用multiset存储k个最小值 1）先存入k个值 2）用multiset中的最大值和当前访问数组元素比较，若小于则把该值从multiset中移除，数组元素插入 3）遍历multiset将k个值存入vector中
注意事项：边界条件的判断，数组为空，k小于1，以及k大于数组元素数目
1 class Solution { 2 public: 3vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { 4 vector<int> result; 5 if(input.empty() || k<1 || input.size()<k) 6 return result; 7 multiset<int> insert_set; 8 9 set<int>::iterator it; //定义前向迭代器10 multiset<int>::reverse_iterator rit; //定义反向迭代器11 for(int i=0;i<input.size();i++)12 {13 14 if(i<k)15 {16 insert_set.insert(input[i]);17 }18 19 else20 {21 rit = insert_set.rbegin();22 if(input[i] < *rit)23 {24 25 insert_set.erase(*rit);26 insert_set.insert(input[i]);27 }28 }29 }30 31 32 for(it = insert_set.begin(); it != insert_set.end(); it++)33 {34 result.push_back(*it);35 }36 return result;37}38 };
