Princeton algorithms course - 如何从一堆袜子中高效地配出袜子?

How to learn algorithms / algorithm / sorting / language-agnostic / matching

昨天我从干净的洗衣店里给袜子配对,发现我做这件事的方式不是很有效。我一直在天真地搜寻-挑选一只袜子,然后“迭代”一堆,以找到那双袜子。这需要遍历的n / 2 * N / 4 = N 2平均/ 8的袜子。

Peter Mortensen



Answer #1

我的特殊情况是我不使用烘干机,只是将衣服挂在普通的干衣机上。挂布需要 O(n) 运算(顺便说一句,我一直在这里考虑垃圾箱包装问题),而从本质上讲,该问题需要线性“额外”空间。当我从水桶中取出新袜子时,如果袜子已经挂好,我会尝试将其挂在袜子对旁边。如果是一对新袜子,我旁边会留一些空间。