这是问错了问题。正确的问题是，我为什么要花时间整理袜子？如果你选择X个货币单位来计算你的空闲时间，那么每年的花费是多少？

通常情况下，这不仅仅是任何空闲时间，这是早晨的空闲时间，你可以躺在床上，或者喝咖啡，或者早点离开，不被交通堵塞。

退一步想办法解决问题通常是好的。

还有一个办法！

找一只你喜欢的袜子。考虑所有相关特征：不同照明条件下的颜色、整体质量和耐久性、不同气候条件下的舒适性以及气味吸收。同样重要的是，它们在储存过程中不应失去弹性，所以天然织物是好的，它们应该可以用塑料包装。

如果左脚和右脚的袜子没有区别，那就更好了，但这并不重要。如果袜子是左右对称的，找到一双袜子是O（1）运算，而对袜子进行排序是近似的O（M）运算，其中M是你家里扔袜子的地方的数量，理想情况下是一个小常数。

如果你选择了一双左右袜子不同的奇装异服，对左脚和右脚的桶进行全桶排序，取O（N+M），其中N是袜子的数量，M与上述相同。其他人可以给出找到第一双袜子的平均迭代次数的公式，但通过盲搜索找到一双袜子的最坏情况是N/2+1，对于合理的N来说，这在天文学上是不太可能的。当用Mk1 Eyeball扫描一堆未分类的袜子时，使用先进的图像识别算法和启发式方法可以加快速度。

因此，实现O（1）袜子配对效率的算法（假设对称袜子）为：

你需要估计你的余生需要多少双袜子，或者直到你退休并搬到更温暖的气候，不再需要穿袜子。如果你还年轻，你还可以估计我们需要多长时间才能在家里拥有袜子分拣机器人，而整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子，以及它的价格，以及它们的送货方式。订购袜子！扔掉你的旧袜子。

另一个步骤3将包括比较几年来一次购买几双同样数量的可能更便宜的袜子的成本，并加上整理袜子的成本。但我要保证：批量购买更便宜！此外，库存袜子的价值会随着股价的上涨而增加，这比你在很多投资中得到的要多。此外，还有存储成本，但袜子确实不会占用壁橱顶部货架上的空间。

问题已解决。所以，只要买一双新袜子，扔掉/捐赠你的旧袜子，在知道你的余生每天都在节省金钱和时间之后，就可以幸福地生活下去。

如果你可以将一双袜子抽象为密钥本身，将另一双袜子作为值，那么我们可以使用哈希来发挥作用。

在你身后的地板上做两个假想的部分，一个给你，另一个给配偶。从袜子堆里取一只。现在，按照以下规则将袜子一只一只地放在地板上。确定袜子是你的还是她的，并查看地板上的相关部分。如果你能在地板上找到这双鞋，就把它捡起来，把它们系起来，或者把它们夹起来，或者在找到一双鞋后做任何你想做的事情，然后把它放在篮子里（把它从地板上取下来）。将其放在相关章节中。重复3次，直到所有袜子都从袜子堆上取下。

说明：

哈希和抽象

抽象是一个非常强大的概念，已用于改善用户体验（UX）。现实生活中与计算机交互的抽象示例包括：

用于在GUI（图形用户界面）中导航以访问地址的文件夹图标，而不是键入实际地址以导航到某个位置。GUI滑块用于控制不同级别的音量、文档滚动位置等。。

哈希或其他不到位的解决方案是不可选择的，因为我无法复制我的袜子（如果可以的话，这可能很好）。

我相信提问者正在考虑使用哈希，这样在放置袜子之前，应该知道袜子的位置。

这就是为什么我建议将放在地板上的一只袜子抽象为哈希键本身（因此不需要复制袜子）。

如何定义哈希键？

如果有不止一双类似的袜子，下面的密钥定义也适用。也就是说，假设有两双黑色男士袜子PairA和PairB，每双袜子都被命名为PairA-L、PairA-R、PairB-L和PairB-R。因此，PairA-L可以与PairB-R配对，但PairA-L和PairB-L不能配对。

假设任何袜子都可以通过以下方式唯一标识，

属性[性别]+属性[颜色]+属性（材质）+属性[类型1]+属性[类别2]+属性[左_右]

这是我们的第一个哈希函数。让我们对这个h1（G_C_M_T1_T2_LR）使用一个简短的符号。h1（x）不是我们的位置键。

消除Left_or_Right属性的另一个哈希函数是h2（G_C_M_T1_T2）。第二个函数h2（x）是我们的位置键！（你身后地板上的空间）。

要定位插槽，请使用h2（G_C_M_T1_T2）。一旦找到了槽，就使用h1（x）来检查它们的哈希值。如果它们不匹配，你就有一对。否则，把袜子扔到同一个槽里。

注意：由于我们在找到一个插槽时删除了一个插槽，因此可以安全地假设最多只有一个插槽具有唯一的h2（x）或h1（x）值。

如果我们每只袜子正好有一对匹配的袜子，那么使用h2（x）来查找位置，如果没有袜子，则需要进行检查，因为可以安全地假设它们是一对。

为什么把袜子放在地板上很重要

让我们考虑一个场景，袜子堆在一起（最坏的情况）。这意味着我们别无选择，只能进行线性搜索来找到一对。

将它们铺在地板上可以提高可见度，从而提高发现匹配袜子（匹配哈希键）的机会。当第三步把袜子放在地板上时，我们的大脑已经下意识地记录了位置。-因此，如果这个位置在我们的内存中可用，我们可以直接找到匹配的配对。-如果没有记住位置，不要担心，然后我们可以一直返回到线性搜索。

为什么从地板上取下这对鞋很重要？

短期人类记忆在需要记忆的项目较少时效果最好。因此，增加了我们使用哈希来识别这对的概率。当使用线性搜索对时，它还将减少要搜索的项目的数量。

分析

情况1：最坏的情况是，Derpina无法记住或直接使用哈希技术在地板上发现袜子。Derp对地板上的物品进行线性搜索。这并不比遍历堆以找到对更糟。比较上限：O（n^2）。比较下限：（n/2）。（当Derpina每捡一只袜子都是上一只的时候）。案例2：德普记得他放在地板上的每一只袜子的位置，每只袜子正好有一双。比较上限：O（n/2）。比较下限：O（n/2）。

我说的是比较操作，从袜子堆里挑选袜子必然是n次操作。因此，实际的下限是n次迭代，n/2次比较。

加快进度

为了获得完美的分数，使Derp获得O（n/2）比较，我建议Derpina，

花更多时间穿袜子来熟悉它。是的，这意味着也要花更多时间穿着德普的袜子。玩记忆游戏，如在网格中找出对，可以提高短期记忆性能，这是非常有益的。

这是否等同于元素清晰度问题？

我建议的方法是用于解决元素区分问题的方法之一，将它们放在哈希表中并进行比较。

考虑到您的特殊情况，即只有一个精确的对，它已经变得非常等价于元素区别问题。因为我们甚至可以对袜子进行分类，并检查相邻袜子是否成对（EDP的另一种解决方案）。

然而，如果给定袜子可能存在不止一双，那么它就偏离了EDP。

如果“移动”操作相当昂贵，而“比较”操作很便宜，并且无论如何都需要将整个集合移动到一个缓冲区中，在那里搜索速度比原始存储快得多。。。只需将排序整合到强制移动中即可。

我发现，将分拣过程整合到晾衣架中，这一过程变得轻而易举。无论如何，我需要拿起每一只袜子，然后把它挂起来（移动），把它挂在绳子上的某个特定位置几乎不需要任何费用。现在，为了不强制搜索整个缓冲区（字符串），我选择按颜色/阴影放置袜子。左边更黑，右边更亮，前面更鲜艳。现在，在我挂上每一只袜子之前，我先看看它的“右边附近”是否已经有一只匹配的袜子——这限制了“扫描”其他2-3只袜子——如果有，我就把另一只挂在旁边。然后，我把它们成对地卷起来，然后在干的时候把它们从绳子上取下来。

现在，这似乎与顶级答案所建议的“按颜色形成桩”没有什么不同，但首先，通过不选择离散桩而是选择范围，我没有问题将“紫色”分类为“红色”还是“蓝色”桩；它只是介于两者之间。然后通过集成两个操作（挂起晾干和分拣），挂起时的分拣开销大约是单独分拣的10%。

这是问错了问题。正确的问题是，我为什么要花时间整理袜子？如果你选择X个货币单位来计算你的空闲时间，那么每年的花费是多少？

通常情况下，这不仅仅是任何空闲时间，这是早晨的空闲时间，你可以躺在床上，或者喝咖啡，或者早点离开，不被交通堵塞。

退一步想办法解决问题通常是好的。

还有一个办法！

找一只你喜欢的袜子。考虑所有相关特征：不同照明条件下的颜色、整体质量和耐久性、不同气候条件下的舒适性以及气味吸收。同样重要的是，它们在储存过程中不应失去弹性，所以天然织物是好的，它们应该可以用塑料包装。

如果左脚和右脚的袜子没有区别，那就更好了，但这并不重要。如果袜子是左右对称的，找到一双袜子是O（1）运算，而对袜子进行排序是近似的O（M）运算，其中M是你家里扔袜子的地方的数量，理想情况下是一个小常数。

如果你选择了一双左右袜子不同的奇装异服，对左脚和右脚的桶进行全桶排序，取O（N+M），其中N是袜子的数量，M与上述相同。其他人可以给出找到第一双袜子的平均迭代次数的公式，但通过盲搜索找到一双袜子的最坏情况是N/2+1，对于合理的N来说，这在天文学上是不太可能的。当用Mk1 Eyeball扫描一堆未分类的袜子时，使用先进的图像识别算法和启发式方法可以加快速度。

因此，实现O（1）袜子配对效率的算法（假设对称袜子）为：

你需要估计你的余生需要多少双袜子，或者直到你退休并搬到更温暖的气候，不再需要穿袜子。如果你还年轻，你还可以估计我们需要多长时间才能在家里拥有袜子分拣机器人，而整个问题变得无关紧要。您需要了解如何批量订购您选择的袜子，以及它的价格，以及它们的送货方式。订购袜子！扔掉你的旧袜子。

另一个步骤3将包括比较几年来一次购买几双同样数量的可能更便宜的袜子的成本，并加上整理袜子的成本。但我要保证：批量购买更便宜！此外，库存袜子的价值会随着股价的上涨而增加，这比你在很多投资中得到的要多。此外，还有存储成本，但袜子确实不会占用壁橱顶部货架上的空间。

问题已解决。所以，只要买一双新袜子，扔掉/捐赠你的旧袜子，在知道你的余生每天都在节省金钱和时间之后，就可以幸福地生活下去。

我提出了另一个解决方案，它不会承诺更少的操作，也不会减少时间消耗，但应该尝试看看它是否能成为一个足够好的启发式方法，在大量袜子配对中提供更少的时间消耗。

前提条件：不能保证有相同的袜子。如果它们的颜色相同，并不意味着它们的大小或图案相同。袜子随机洗牌。袜子的数量可能是奇数（有些不见了，我们不知道有多少）。准备记住一个变量“index”并将其设置为0。

结果将有一个或两个桩：1。“匹配”和2。“缺少”

启发式：

找到最与众不同的袜子。找到匹配项。如果没有匹配项，请将其放在“缺失”堆上。从1开始重复。直到没有最与众不同的袜子。如果袜子少于6只，请转到11只。盲目地将所有袜子与邻居配对（不要打包）找到所有匹配的对，将其打包并将打包的对移动到“匹配”的堆中；如果没有新的匹配项-将“索引”增加1如果“index”大于2（这可能取决于袜子的值因为袜子数量越多盲目配对）进入11打乱其余的转到1忘记“索引”挑选一只袜子查找其配对如果没有袜子，就把它移到“失踪”的那一堆如果找到匹配项，将其配对，将其打包并移动到“匹配”堆中如果还有不止一只袜子，那就去12只如果只剩下一个，请转到14满意的微笑：）

此外，还可以添加检查袜子是否损坏，就像移除袜子一样。它可以插入2到3之间，13到14之间。

我期待听到任何经验或更正。

拿起第一只袜子放在桌子上。现在再挑一只袜子；如果它与第一个拾取的匹配，请将其放在第一个拾取上。如果没有，把它放在桌子上，离第一个小距离。挑选第三只袜子；如果它与前两个匹配，请将它放在它们的上面，或者将它放置在距离第三个的一小段距离处。重复上述步骤，直到你捡起所有袜子。