这周233酱和多年未见的老友聚了聚，除了变秃了点，大家都还是当初的模样儿～
我只好把从果壳看来的防秃指南告诉她。虽然没有一招制胜的卵方法，但也打消了我写防秃水文的念头...
从知乎「有哪些令人拍案叫绝的算法？」话题下看到一个简单有趣的回答，是原作者「时宇电」面试腾讯的一道算法题。233酱的思考路线和作者的差不多，这里整理后分享给大家～
题目描述
有一种玻璃杯从一栋100层的大楼扔下，该种玻璃杯超过某一层楼会摔碎。
现在给你两个杯子，问确定最低摔碎的楼层需要摔多少次？
题目分析
这道题的假设是：最低摔碎的楼层可能是每一层楼，且概率相同。我们需要找一种方法，使得定位到[1-100]之间的任意一个数都是快速的。
解题思路
最简单的方法是用一个杯子从第一层开始，不断一层层的往上试。但是这样的时间复杂度是O(n)。直觉也告诉我们想放大步子扔。
因为我们有两个杯子，可以考虑成一个杯子Cup1不断扔直到破碎，它用来确定最低摔碎的楼层在什么范围，
另一个杯子Cup2再此基础上一层层的扔。用来准确确定最低摔碎的楼层是多少。
如果凭空想象，我们可能会想到二分法，每次隔5个楼层扔，10个楼层扔...
可是我们马上也应该会想到这么分的不妥之处在于：
确定最低摔碎的楼层所需次数是不均匀分布的。
我们再来看：每次扔的楼层间隔会带来什么影响？
确定最低摔碎的楼层：
总次数 = Cup1扔的次数 + Cup2扔的次数
楼层间隔越大，Cup2需要扔的次数越多。
相同楼层间隔下：最低摔碎的楼层越高，Cup1需要扔的次数越多，Cup2需要扔的次数可认为相同。
我们的目的其实是需要尽可能保证：不管最低摔碎的楼层是第一层还是第99层，扔的总次数都尽可能一致且减少。
如果小伙伴有看我上篇文章中LSMT分层步隆过滤器的实现，有没有受到启发？
这里我们可以使Cup1需要扔的楼层间隔递减，这样可改善高楼层所需Cup1/Cup2扔的次数。
假设第一次扔的楼层间隔为X，此后依次递减1层，直到楼层间隔为2.则：
x+(x-1)+(x-2)+...+2 >=100
求解出答案为14。
网友评论