Leetcode1833. 雪糕的最大数量

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++;
            }
            else
                break;
        }
        return ice_cream;
    }
};
// @lc code=end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

结果：

复杂度分析：

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

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