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