Tag: 分类与

如何有效地从一堆袜子配对？

昨天我是从干净的洗衣店袜子配对，并找出我做的方式不是很有效。 我正在做一个天真的search – 挑一只袜子，“迭代”一堆，以find它的一对。 这要求平均迭代n / 2 * n / 4 = n 2/8袜子。 作为一名计算机科学家，我在想我该怎么办？ sorting（根据大小/颜色/ …）当然想到实现O（NlogN）的解决scheme。 哈希或其他非原地解决scheme不是一种select，因为我无法复制我的袜子（尽pipe如果我可以很好）。 所以，这个问题基本上是： 给定一堆n对袜子，包含2n元素（假设每个袜子只有一对配对），那么将它们有效配对到对数额外空间的最佳方法是什么？ （如果需要的话，我相信我可以记住这个数量的信息。） 我将非常感谢一个解决以下问题的答案： 大量袜子的一般理论解决scheme。 袜子的实际数量并不大，我不相信我的配偶和我有30多双。 （把袜子和她的袜子区分开来是相当容易的，这个也可以使用吗？） 这是否相当于元素清晰度问题 ？