1

考虑一组有 n 个瓶子的 A 和一组有 n 个盖子的 B，这样 A 中的每个瓶子在 B 中都有唯一的盖子。但是 A 中的瓶子和 B 中的盖子看起来都一样。可以进行的唯一比较是 A 中的瓶子和 B 中的瓶盖配对 (a,b)，并测试 a 的螺纹是否更小、更大或与 b 的螺纹完美。

给出一个有效的算法来匹配所有瓶子和它们的盖子。

PS：这似乎我没有做任何事情来获得解决方案，相信我，我做到了。请给我一个答案。

4

1 回答 1

1

不错的问题，但正如在它似乎是家庭作业之前指出的那样，为什么你不尝试这样的事情：

你应该为每个瓶子循环（没有任何逻辑顺序）你应该有一种结构的盖子，它是一个动态排序的盖子集合数组，这个数组被初始化只有一个元素（即集合 B）。

并且对于每个瓶子，当您获得“潜在”的一组瓶盖时，您应该使用二进制搜索在您的阵列中旅行，您逐个检查瓶盖

  • 如果瓶盖较小，则将其放在同一组中（将其标记为不再为该瓶服用
  • 对于第一个更大的上限，您需要在当前组和下一个组之间插入一个组并将上限放在那里
  • 对于以下更大的上限，您将它们放入先前创建的集合中
  • 如果您找到正确的瓶盖，则您有一个匹配并继续使用同一瓶拆分该组的剩余瓶盖，然后您继续使用下一瓶
  • 如果在当前集合中您没有找到任何上限，但您检查的所有上限都更大，您可以使用二进制搜索来搜索较低的上限
  • 如果在当前集合中您没有找到任何上限，但您检查的所有上限都较小，您可以使用二进制搜索来寻找更大的上限

编辑：我已经看到发布的评论，实际上它是从 两组项目中重复的。集合 A 的每个元素在集合 B 中唯一匹配。在 O(nlogn) 时间内将集合 A 的每个项目与集合 B 中的项目匹配 ，解决方案在这里解释 http://www.wisdom.weizmann.ac.il/~ naor/PUZZLES/nuts_solution.html

和我的很相似，但瓶子也可以隔开。

于 2013-10-02T21:28:51.273 回答