题目链接1833. 雪糕的最大数量中等算法原理解法一贪心排序39ms击败61.05%时间复杂度O(n logn)贪心从低价格到高价格购买买的雪糕最多思路就很简单了1️⃣排序2️⃣遍历 costs 每一个值 x3️⃣用兜里的钱买这个 x4️⃣买完不该人家的就计数5️⃣买完发现还欠人家直接 break 结束避免后续无意义的遍历6️⃣返回 计数结果 cnt解法二贪心计数排序5ms击败90.44%时间复杂度O(N)计数排序的知识可参考这篇博客⬇️Java数据结构——9.排序《干货笔记》通过计数数组间接实现了 按价格从小到大处理 的效果等价于对 cost 数组完成了升序排序计数排序的本质利用数组统计每个值出现的次数再按值的大小顺序遍历计数数组间接得到有序序列不是比较排序而是基于 值域统计 的排序思想1️⃣确定数据的值域范围2️⃣统计每个值的出现次数计数核心3️⃣按值从小到大遍历等价于排序后遍历Java代码class Solution { //1833. 雪糕的最大数量 //解法一贪心排序 public int maxIceCream(int[] costs, int coins) { Arrays.sort(costs); int cnt0; for(int x:costs){ coins-x; if(coins0) cnt; else break; } return cnt; } }class Solution { //1833. 雪糕的最大数量 //解法二贪心计数排序 public int maxIceCream(int[] costs, int coins) { int mx0; for(int x:costs) mxMath.max(mx,x); //统计计数数组 int[] cntnew int[mx1]; for(int x:costs) cnt[x]; //按照价格从低到高购买 int ret0; //从低费往高费遍历且费用要兜里的钱 for(int price1;pricemxpricecoins;price){ //能买的个数min(库存能购买的最大数目) int numMath.min(cnt[price],coins/price); //买 num 根雪糕 coins-price*num; retnum; } return ret; } }
