What is an efficient way to match n items with corresponding n items

This question already has an answer here:

Two sets of items. Each element of set A a unique match in set B. Match each item of set A to item in set B in O(nlogn) time 1 answer

---

Nice problem but as it was pointed before it seems a Homework, why you don't try something like this:

you should cycle for each bottle (without any logical order) you should have the caps in a kind of structure that is a dynamic sorted array of caps sets, this array is initialized having only one element (that is the set B).

and for each bottle you should travel in your array using Binary Search when you get the "potential" set of caps, you check cap by cap

if the cap is smaller you let it in the same set (marking it to not taking again for that bottle

for the first greater cap, you need to insert a set between the current set and the next one and put the cap there

for the following greater caps you put them in the previously created set

if you find the correct cap you have a match and continue splitting with the same bottle the remaining caps of the set, after that you continue with the next bottle

if in the current set you dont find any cap, but all the caps you have checked are greater you can travel using binary search for the lower caps

if in the current set you dont find any cap, but all the caps you have checked are lesser you can travel using binary search for the bigger caps

Edit: i have seen the posted coment and indeed it is duplicate from Two sets of items. Each element of set A a unique match in set B. Match each item of set A to item in set B in O(nlogn) time and the solution is explained here http://www.wisdom.weizmann.ac.il/~naor/PUZZLES/nuts_solution.html

quite similar to mine, but bottles can be partitioned also.

链接地址: http://www.djcxy.com/p/12204.html

上一篇: 在PHP中验证信用卡的最佳方式是什么？

下一篇: 什么是使n个项目与相应的n个项目匹配的有效方式