Re: [問題] 在2n大小的陣列中，挑出n個元素排成陣列

看板C_and_CPP (C/C++)作者LPH66 ((short)(-15074))時間16年前 (2009/02/25 19:00)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串2/2 (看更多)

※ 引述《poc7667 (poc)》之銘言： : 在2n大小的陣列中，挑出n個元素排成陣列。 : 而這n個元素所形成的陣列，第i個元素，是原本的整個陣列第2i個大 : 比如說原本陣列A[2N] <-unsorted : 而我們選出的陣列叫做B[N] : B[6]這個元素就是原本整個陣列的第12大。 : 目前我只想到用quick sort下去解，但是time complexity只能到 NlogN : 請問有更快的解法嗎？ : 這不是作業，只是考古題的題目，最近應付考試:) : 謝謝假設對這個問題我們有 O(N) 的解法。顯然將第2i大改成第2i小不會改變時間複雜度這時對 A 做一次"第2i大"的問題得到結果 B 對 A 做一次"第2i小"的問題得到結果 C 那麼由於A的大小是偶數故 B 和 C 兩者恰好形成 A 的一個分割因此將 B 和 C 做 Merge-sort 的合併步驟即可得到 A 的排序結果如果假設成立那以上演算法將會在 O(N) 時間內把 A 排好因此若限定排序為比較型排序的話則產生矛盾 (比較型排序的 time complexity 底限為 O(NlogN)) 若不限定的話利用 O(N) 的(限定情形下的)排序 (例如radix-sort) 原問題的確存在 O(N) 的做法 (也就是排好再抓出來就是了XD) -- 像這種和排序有關的問題基本想法就是去證不用排序不會比較好也就是說如果真的有比較好的答案那用它可以反過來打破排序已知的結論 (就像上面的做法一樣) -- 是說這篇貌似比較適合 Prob_Solve 版...XD -- "LPH" is for "Let Program Heal us".... -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.84 ※ 編輯: LPH66 來自: 140.112.30.84 (02/25 19:00)