网站程序建设中国新闻网

Every day a Leetcode

题目来源：1833. 雪糕的最大数量

解法1：贪心 + 排序

本题唯一的难点在于计数排序。

计数排序详解：C++算法之计数排序

为了尽可能多的买到雪糕，我们选择从价格低的雪糕开始买，统计能够买到的雪糕的数量。

代码：

/** @lc app=leetcode.cn id=1833 lang=cpp** [1833] 雪糕的最大数量*/// @lc code=start
class Solution
{
private:
#define MAX_ELEMENT 1e5
#define MAX_N 1e5 + 1// 计数排序void CountSort(vector<int> &vec){vector<int> cnt(MAX_N, 0);for (int &v : vec)cnt[v]++;int index = 0;for (int i = 1; i <= MAX_ELEMENT; i++)for (int j = 0; j < cnt[i]; j++){vec[index] = i;index++;}}public:int maxIceCream(vector<int> &costs, int coins){int ice_cream = 0;CountSort(costs);for (int &cost : costs){if (coins >= cost){coins -= cost;ice_cream++;}elsebreak;}return ice_cream;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n + K)，其中 n 是数组 costs 的长度，K 是计数数组 cnt 的长度。

空间复杂度：O(n + K)，其中 n 是数组 costs 的长度，K 是计数数组 cnt 的长度。