※ 引述《aqua269 (virtual)》之铭言：
: https://imgur.com/YTGGKPa
: 题目要求在O(n)的时间内找出被取走的nut所配对的bolt
: https://courses.engr.illinois.edu/cs473/sp2017/notes/02-nutsbolts.pdf
: 有找到一篇似乎是有关随机算法的部分?
: 如果是找最大，我觉得还算简单，就只要先随机挑一组，
: 然后留下最大的，重复直到剩下最大的bolt或nut，
: 再花O(n)找到配对的另一半就好。
: 但是现在题目是要求一个随机的nut所配对的bolt，没什么想法QQ
: 而且我对期望值跟机率一直不是很熟，
: 请问有没有比较好的算法来解决?
: 感谢!
I think an algo similar to the one for "selection problem" might work.
For convenience, number the bolts and nuts from 1 to n, where n is the number
of nuts/bolts.
So for example, n = 5
bolts = [4, 3, 1, 5, 2]
nuts = [3, 2, 1, 5, 4]
Now we take out "2" from the bolts, the problem is to find "2" in the nuts
in expected O(n) time.
The algorithm works as follows:
1. Pick a nut randomly and use it to partition the bolts.
(call it "pivot nut")
2. If the corresponding bolt is not found while partitioning,
then just return the nut. Done.
3. Else, use the matching bolt to parition the nuts.
If #(nuts that are < pivot nut) != #(bolts that are < pivot bolt),
then recurse with the nuts and bolts that are smaller.
Else, recurse with the nuts and bolts that are larger.
The above algorithm is quite similar to selection algorithm, and it will run
in expected O(n) time.
Let's run the algorithm on the example mentioned above.
Initially, bolts = [4, 3, 1, 5]
nuts = [3, 2, 1, 5, 4]
Pick nut of "1" as pivot. (Picking is random.)
-> bolts = [1, 4, 3, 5]
Since the bolt of "1" is found, use it to partition the nuts
-> nuts = [1, 3, 2, 5, 4]
Since we have unequal number of nuts and bolts that are larger than "1",
so by the algorithm, we will recurse with
bolts = [4, 3, 5]
nuts = [3, 2, 5, 4]
("1" is discarded)
Now pick nut of "3" as pivot and partition the bolts
-> bolts = [3, 4, 5]
Since the bolt of "3" is found, so will partition the nuts with it.
-> nuts = [2, 3, 5, 4]
Since we have unequal number of bolts and nuts that are smaller than the pivot,
so will, again, recurse with them. ("3", "4" and "5" are discarded.)
bolts = []
nuts = [2]
Finally, we pick nut of "2" to partition bolts, and no corresponding
bolt is found, so the answer is nut of "2".