[理工] 演算法 排序

[TNC (code)]

1.You are given n bolts of different width and their corresponding nuts.
  Each time, you can try one bolt and one nut together and determine
  whether the nut is too large, too small or an exact fit.
  You cannot compare the width of two bolts or two nuts.
  Design an algorithm to match each bolt to its corresponding nut
  with average running time O(n log n)
  請問這題是類似quick sort的想法嗎?

2.Given n numbers a1,a2,...an Design a liner time algo to find all numbers
  that occur more than floor(n/5) times.
  目前這題只想到暴力解，但顯然不是出題者要的答案。

  希望高手解惑

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.62.228
→ chunhsiang:2. 找第一大 第1/5大 第2/5大... 第4/5大 O(n)
→ chunhsiang:計算第一大出現次數 O(n) 第1/5大出現次數 O(n) ...
→ chunhsiang:總共 O(n)
→ chunhsiang:1. 兩個類別有同樣的屬性 但規定同類不能比較
→ chunhsiang:那就拿另外一類當PIVOT
→ chunhsiang:另外一個PRATITION後會匹配到一組 再拿那組的去對
→ chunhsiang:另外一邊PRATITION
→ chunhsiang:交互作類似QUICK sort