算法笔试模拟题精解之“钱庄”

算法笔试模拟题精解之“钱庄”

贡献者 | 张鹏飞

简介：可以先分析示例是如何实现的，以此为突破点。

题目描述

等级：中等

知识点：贪心

查看题目：钱庄

钱庄每天能够收到很多散钱，第 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 为钱币数 ;

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：钱庄