偶尔，我的妻子带我去一家真正的超市，带着购物 list (她给我写了一张纸，或者发短信给我)。
我想知道是否有一种快速的方法来填充列表，而无需将整个 super 迭代数十次，直到我相信我已经掌握了所有内容。
(我发现这个问题对生活很有帮助:pair-socks-from-a-pile-efficiently，希望能在自己的情况下借助社区的帮助)
I don't know/remember where each item is located in the supermarket, and the list I'm given is never sorted (for example, vegetables are listed all over the list, and not one after the other). Also, usually I get continuously text messages with more and more items to buy, while I'm still in the super.
我的方法是规划一条路径，确保我遍历整个超市，并在走这条路径时从列表中挑选商品。
我想到的两种方式:
- foreach item in the super
(n)我通过:检查我的列表中是否有这样的项目(m)，会给我一个O( n*m)共谋，效率不高。 - 将商店“划分”成行
(p):站在每一行的开头，我可以阅读标志或查看我应该在那里找到哪种商品，而不是迭代我的列表，尝试记住我应该在该行中找到的列表中的所有项目。而不是走那一行并将这些项目添加到我的购物车，应该给我O(p*m)同谋。 但这从未真正发生过:我不记得我的列表中我期望在该行中找到的四个项目中的三个以上，即使我记住了，我也经常忘记一个项目并且有再次使用此算法(假设q次)，得出:O(q*p*m)。
我想补充几点意见:
- 例如，当我到达蔬菜区时，我发现自己多次浏览该区，因为我的妻子是一位出色的厨师，并且在列表中添加了各种蔬菜
(v)。当然，我不记得所有这些蔬菜，也不想在市场上的每一种蔬菜旁边停下来(或者我应该吗？)，检查我是否在我的 list 上。 - 划掉我放入购物车中的每件商品(或制作一个包含所有我还没有的商品的新列表)对我来说非常耗时，所以我宁愿每次都浏览整个列表试着看看我是否还有要添加到购物车的商品。
- 另一种情况是您在全家度假前上车。你记得你忘了带这个，但是，跑回你的房子，拿了一些这些东西，忘记了其他东西然后又回去了。这是一个类似的案例吗？
最佳答案
查找重排时间here , 我最初的想法是花时间为您绘制常用元素的 map 是没有用的。 (他们经常重新安排过道)。
对于沿着这条路走下去的任何想法 - 行不通......
关于algorithm - 带着购物 list 逛超市，最快买到所有商品？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30789366/