在线编程介绍
阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：https://developer.aliyun.com/coding
本文为大家介绍其中的 第74题：钱庄 的题目解析，具体如下：
题目描述
等级：中等
知识点：贪心
查看题目：钱庄
钱庄每天能够收到很多散钱，第i个散钱的值2^wi。为了便于管理，钱庄每天都会向中央银行申请兑换钱币，假设钱庄有一些散钱使得2^k1+2^k2+...+2^km=2^x（x为非负整数），那么就可以将这些散钱兑换成一个大钱币，问在钱庄收到的这些散钱最终最少能变成几个钱币？
输入一个整数n，表示一共有n个钱币(1 <= n <= 10^6)；再输入n个整数wi，表示有价值2^wi(0 <= wi <= 10^6)的钱币。
输出兑换后最少的钱币数
示例1
输入：
4
[1, 1, 2, 3]
输出：
1
注意
2^1+2^1+2^2+2^3=2^4，因此兑换后最少为一个钱币
解题思路一
大致思路：对于[1, 1, 2, 3]样例，答案1是怎么算出来的？按照题目的思路，应该这样算：2^1+2^1+2^2+2^3=2^4,因此为1，但是如果这样做，肯定会超时，我是这样算的：对于底数为2幂数相同的两个数想加，是不是底数不变，幂加1，因此两个1组成一个2，此时共有两个2，这两个2组成一个3，此时共有两个3，两个三组成一个4，最后只剩一个4，因此答案为1.
具体过程：遍历一遍m找出m中的最大数max，定义一个数组arr[max+2],用于统计出m数组中，每个数字出现的次数，即arr[m[i]]++（m中的元素为下标，arr数组中保存出现的次数）;
再次遍历arr数组(0<=i<=max)，如果当前元素arr[i]==0，那就下一个，
如果不为0，arr[i+1]+=arr[i]/2;(每两个arr[i]就能凑一个arr[i+1])
如果arr[i]为奇数，那说明剩余一个arr[i]，这最后也就剩下了，所以ans++；
遍历完后if(arr[max+1]!=0) ans++;然后return ans;
注意：加粗部分一定要理解
解题思路二：贪心
遍历钱币数组m, 只要数组中的当前元素x可以兑换一个大金币(有两个以上相同的钱币)就自底向上兑换, 直到无法兑换;
遍历结束后, 对剩下的钱币个数做统计(而上述操作保证了所有钱币均不可兑换);
复杂度分析
空间复杂度
开辟了100000大小的map数组(因为价值wi取值为:0 <= wi <= 10^6)
所以空间复杂度为: O(100000) ~ O(1)
时间复杂度
针对钱币数组遍历一次, 每一次会做自底向上的钱币转换遍历;
所以最差情况下时间复杂度, 每次都会自底向上发生转换;
所以时间复杂度最差为: O(n^2)， 其中n为钱币数;
看完之后是不是有了想法了呢，快来练练手吧>>查看题目：钱庄
