题解 | #最小的K个数#

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;	// 创建储存结果的数组
	  // map数据结构会根据键的大小自动排序
	  // 键：input内的元素	值：对应元素出现的次数
        map<int,int> mp;
	  // 将input中的元素加入到mp中，
        for(int i = 0; i < input.size(); ++i){
            mp[input[i]]++;
        }
	  // 依次从mp中取键值对，此时根据键的大小已经排好序了
        for(auto it : mp){
		  // 当res的大小比k小时，进入while循环，往res中加数据
            while(res.size() < k){
			  // 对应的键加几次进去res，取决于对应的值
                for(int i = 0; i < it.second; ++i){
                    res.push_back(it.first);
                    if(res.size() == k) break;	// 每加进一个数据，判断res的大小跟k的大小，res的大小等于k，则直接跳出循环
                }
                break;	// 跳出while循环，避免反复往res中加入相同的值
            }
        }
        return res;
    }
};