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
而且我對期望值跟機率一直不是很熟，
請問有沒有比較好的演算法來解決?
感謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.114.233.76 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1647531181.A.5AC.html