Home Page

题目描述

官方描述(中文)
2021/09/03每日一题

思路

大根堆,优先队列,其他的没有啥难度

代码

class Solution {
public:
   	vector<int> smallestK(vector<int>& arr, int k) 
	{
		if (k <= 0)return{};
		vector<int>res;
		std::priority_queue<int, vector<int>, std::less<int>>queMin;
		for (auto i : arr)
		{
			if (queMin.size() == k)
			{
				if (queMin.top() > i)
				{
					queMin.pop();
					queMin.push(i);
				}
			}
			else
			{
				queMin.push(i);
			}
		}
		while (!queMin.empty())
		{
			res.push_back(queMin.top());
			queMin.pop();
		}
		return res;
	}
};

运行结果

image.png

Q.E.D.