【LeetCode】雪糕的最大数量 Java 题解
题目描述
夏日炎炎,小男孩 Tony 想买一些雪糕消消暑。
商店中新到 n 支雪糕,用长度为 n 的数组 costs 表示雪糕的定价,其中 costs[i] 表示第 i 支雪糕的现金价格。Tony 一共有 coins 现金可以用于消费,他想要买尽可能多的雪糕。
给你价格数组 costs 和现金量 coins ,请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。
注意:Tony 可以按任意顺序购买雪糕。
复制代码
思路分析
夏日炎炎,到了吃雪糕的季节,但是不要贪多哦~冷静分析题目,一句话描述题意就是 求用给定的 coins 可以买到最多数量的雪糕是多少?
理解题意之后,根据题目提示 可以按任意顺序购买雪糕 ,先排序,然后采用贪心思想解决问题。
代码
复制代码
总结
上述代码的时间复杂度是 O(n * log (n)), 空间复杂度是 O(log n)
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/088196692f40da138ee2e2ec7】。文章转载请联系作者。
评论