Re: [理工] 演算法相關:Bolts and nuts
: 題目要求在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".
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.166.250.208 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1647560451.A.3A9.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：