英文:
n balls and n cups algorithm design
问题
你有n个球和n个杯子。每个杯子都有特定的重量，一旦放入球，它会告诉你球是太重、太轻还是合适。你不能直接比较球的重量。存在一种完美的球与杯子之间的配对。设计一个期望的nlogn算法来找到这种配对。提示：修改快速排序。
我已经考虑了很长时间这个问题，但没有头绪。有没有一种有效的方法来比较两个球的重量，或者我在想错方向？有人可以给个提示吗？
英文:
You are given n balls and n cups. Each cup holds a particular weight, and once a ball is placed in it tells you whether the ball is too heavy or light or just right. You can’t compare the weight of the balls directly. A perfect pairing between balls and cups exist. Design an expected nlogn algorithm to find the pairing. Hint: modify quicksort.
I’ve thought about this problem for a long time with no leads.
Is there a efficient way to compare the weight of two balls, or am I thinking about this wrong? Can someone please give a hint?
答案1
得分: 1
如果你将所有球与随机选择的一个杯子进行比较，你会找到相匹配的球，而其他球将被分成高的和低的两部分。你可以使用相匹配的球以类似的方式来分割杯子。然后你基本上就得到了随机快速排序。
英文:
If you compare all balls with a single randomly picked cup, you will find the matching ball, and the other balls will be partitioned into those higher and those lower. You can use the matching ball to also partition the cups in a similar way. Then you have essentially randomized quicksort.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论