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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1647531181.A.5AC.html