1833-雪糕的最大数量

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:30 2023-09-13 16:06:30 Updated    

夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。

商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。Tony
一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。

注意： Tony 可以按任意顺序购买雪糕。

给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

你必须使用计数排序解决此问题。

示例 1：

**输入：** costs = [1,3,2,4,1], coins = 7
**输出：** 4
**解释：** Tony 可以买下标为 0、1、2、4 的雪糕，总价为 1 + 3 + 2 + 1 = 7

示例 2：

**输入：** costs = [10,6,8,7,7,8], coins = 5
**输出：** 0
**解释：** Tony 没有足够的钱买任何一支雪糕。

示例 3：

**输入：** costs = [1,6,3,1,2,5], coins = 20
**输出：** 6
**解释：** Tony 可以买下所有的雪糕，总价为 1 + 6 + 3 + 1 + 2 + 5 = 18 。

提示：

  • costs.length == n
  • 1 <= n <= 105
  • 1 <= costs[i] <= 105
  • 1 <= coins <= 108

方法一：排序 + 贪心

在给定硬币数量 coins 的情况下，要买到最多的雪糕，应该买最便宜的雪糕，理由如下。

假设购买最便宜的雪糕，在总价格不超过 coins 的情况下最多可以购买 k 支雪糕。如果将 k 支最便宜的雪糕中的任意一支雪糕替换成另一支雪糕，则替换后的雪糕的价格大于或等于替换前的雪糕的价格，因此替换后的总价格大于或等于替换前的总价格，允许购买的雪糕数量不可能超过 k。因此可以买到的雪糕的最大数量为 k。

由此可以得到贪心的解法：对数组 costs 排序，然后按照从小到大的顺序遍历数组元素，对于每个元素，如果该元素不超过剩余的硬币数，则将硬币数减去该元素值，表示购买了这支雪糕，当遇到一个元素超过剩余的硬币数时，结束遍历，此时购买的雪糕数量即为可以购买雪糕的最大数量。

[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        Arrays.sort(costs);
        int count = 0;
        int n = costs.length;
        for (int i = 0; i < n; i++) {
            int cost = costs[i];
            if (coins >= cost) {
                coins -= cost;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int MaxIceCream(int[] costs, int coins) {
        Array.Sort(costs);
        int count = 0;
        int n = costs.Length;
        for (int i = 0; i < n; i++) {
            int cost = costs[i];
            if (coins >= cost) {
                coins -= cost;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        sort(costs.begin(), costs.end());
        int count = 0;
        int n = costs.size();
        for (int i = 0; i < n; i++) {
            int cost = costs[i];
            if (coins >= cost) {
                coins -= cost;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cmp(int *a, int *b) {
    return *a - *b;
}

int maxIceCream(int *costs, int costsSize, int coins) {
    qsort(costs, costsSize, sizeof(int), cmp);
    int count = 0;
    int n = costsSize;
    for (int i = 0; i < n; i++) {
        int cost = costs[i];
        if (coins >= cost) {
            coins -= cost;
            count++;
        } else {
            break;
        }
    }
    return count;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
var maxIceCream = function(costs, coins) {
    costs.sort((a, b) => a - b);
    let count = 0;
    const n = costs.length;
    for (let i = 0; i < n; i++) {
        const cost = costs[i];
        if (coins >= cost) {
            coins -= cost;
            count++;
        } else {
            break;
        }
    }
    return count;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
func maxIceCream(costs []int, coins int) (ans int) {
    sort.Ints(costs)
    for _, c := range costs {
        if coins < c {
            break
        }
        coins -= c
        ans++
    }
    return
}

复杂度分析

  • 时间复杂度：O(n \log n)，其中 n 是数组 costs 的长度。对数组排序的时间复杂度是 O(n \log n)，遍历数组的时间复杂度是 O(n)，因此总时间复杂度是 O(n \log n)。

  • 空间复杂度：O(\log n)，其中 n 是数组 costs 的长度。空间复杂度主要取决于排序使用的额外空间。

方法二：计数排序 + 贪心

由于数组 costs 中的元素不会超过 10^5，因此可以使用计数排序，将时间复杂度降低到线性。

使用数组 freq 记录数组 costs 中的每个元素出现的次数，其中 freq}[i] 表示元素 i 在数组 costs 中出现的次数。仍然使用贪心的思想，买最便宜的雪糕，因此按照下标从小到大的顺序遍历数组 freq，对于每个下标，如果该下标不超过剩余的硬币数，则根据下标值和该下标处的元素值计算价格为该下标的雪糕的可以购买的最大数量，然后将硬币数减去购买当前雪糕的花费，当遇到一个下标超过剩余的硬币数时，结束遍历，此时购买的雪糕数量即为可以购买雪糕的最大数量。

[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxIceCream(int[] costs, int coins) {
        int[] freq = new int[100001];
        for (int cost : costs) {
            freq[cost]++;
        }
        int count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (coins >= i) {
                int curCount = Math.min(freq[i], coins / i);
                count += curCount;
                coins -= i * curCount;
            } else {
                break;
            }
        }
        return count;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    public int MaxIceCream(int[] costs, int coins) {
        int[] freq = new int[100001];
        foreach (int cost in costs) {
            freq[cost]++;
        }
        int count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (coins >= i) {
                int curCount = Math.Min(freq[i], coins / i);
                count += curCount;
                coins -= i * curCount;
            } else {
                break;
            }
        }
        return count;
    }
}
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxIceCream(vector<int>& costs, int coins) {
        vector<int> freq(100001);
        for (int& cost : costs) {
            freq[cost]++;
        }
        int count = 0;
        for (int i = 1; i <= 100000; i++) {
            if (coins >= i) {
                int curCount = min(freq[i], coins / i);
                count += curCount;
                coins -= i * curCount;
            } else {
                break;
            }
        }
        return count;
    }
};
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxIceCream(int *costs, int costsSize, int coins) {
    int freq[100001];
    memset(freq, 0, sizeof(freq));
    for (int i = 0; i < costsSize; i++) {
        freq[costs[i]]++;
    }
    int count = 0;
    for (int i = 1; i <= 100000; i++) {
        if (coins >= i) {
            int curCount = fmin(freq[i], coins / i);
            count += curCount;
            coins -= i * curCount;
        } else {
            break;
        }
    }
    return count;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var maxIceCream = function(costs, coins) {
    const freq = new Array(100001).fill(0);
    for (const cost of costs) {
        freq[cost]++;
    }
    let count = 0;
    for (let i = 1; i <= 100000; i++) {
        if (coins >= i) {
            const curCount = Math.min(freq[i], Math.floor(coins / i));
            count += curCount;
            coins -= i * curCount;
        } else {
            break;
        }
    }
    return count;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func maxIceCream(costs []int, coins int) (ans int) {
    const mx int = 1e5
    freq := [mx + 1]int{}
    for _, c := range costs {
        freq[c]++
    }
    for i := 1; i <= mx && coins >= i; i++ {
        c := min(freq[i], coins/i)
        ans += c
        coins -= i * c
    }
    return
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

复杂度分析

  • 时间复杂度：O(n + C)，其中 n 是数组 costs 的长度，C 是数组 costs 中的元素的最大可能值，这道题中 C=10^5。

  • 空间复杂度：O(C)，其中 C 是数组 costs 中的元素的最大可能值，这道题中 C=10^5。需要使用 O(C) 的空间记录数组 costs 中的每个元素的次数。

 Comments
On this page
1833-雪糕的最大数量