这是一道有趣的数学方面的问题。
今天刚好是中秋节,我们就不管月宫的兔子,来数数森林中的兔子吧。
比如我们遇到了2只兔子说7,那么他们俩可能是颜色一样的,也就是这个颜色兔子得有8只。
比如我们遇到了8只兔子说7,那么这8只可能是颜色一样的,也就是这个颜色兔子得有8只。
比如我们遇到了9只兔子说7,那么不可能是颜色都一样的,也就是这个颜色兔子至少得有16只。
比如我们遇到了17只兔子说7,那么不可能是颜色都一样的,也就是这个颜色兔子至少得有24只。
我们会发现规律,兔子的只数,取决于他们说的数字和多少只说了同样的数字。
1个7,为8只。
2个7,为8只。
3个7,为8只。
4个7,为8只。
5个7,为8只。
6个7,为8只。
7个7,为8只。
8个7,为8只。
9个7,为16只。
也就是拿报号的只数除以8,除完得是向上去整,最后乘以8。
那么向上去整怎么做呢?以8为例,有两种方案:
((报号只数 – 1) / 8) + 1 这样就向上去整了最终结果+1,但也考虑刚好整除,所以预先-1。
(报号只数 + (8 – 1)) / 8 这样也可以向上去整,因为刚好整除的加上7也不够多一位。
处理完每一种兔子报的数字和兔子的数量的关联系后,我们就差用什么数据结构来装这些兔子报的号码了。
把数字都存起来,然后再数,时间复杂度会较高。
我们用桶排序来装的话,可以实现,但怕某一只兔子报个很大的数字,这样我们得开很大的数组。空间又是问题。
所以最佳方案应该是哈希表,如果这个数字有,那就这个数字的数量+=1,如果没有,就建立键值对,值开始就是1。
最终根据哈希表的迭代器来加总输出。
真是一道有趣的题目,祝大家中秋节快乐。