→ windincloud:問一下 那照你這樣說的說 所有的b[n] 必落在A[2*n] 02/25 17:19
→ windincloud:也就是說原先已排序後A[2n+1]是不會出現在B[n]中囉~ 02/25 17:20
→ windincloud:若我的想法沒錯的話~ 那這樣就是A[] sorting問題囉~ 02/25 17:22
在2n大小的陣列中，挑出n個元素排成陣列。
而這n個元素所形成的陣列，第i個元素，是原本的整個陣列第2i個大
比如說原本陣列A[2N] <-unsorted
而我們選出的陣列叫做B[N]
B[6]這個元素就是原本整個陣列的第12大。
目前我只想到用quick sort下去解，但是time complexity只能到 NlogN
請問有更快的解法嗎？
這不是作業，只是考古題的題目，最近應付考試:)
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.198.248
※ 編輯: poc7667 來自: 140.113.198.248 (02/25 16:59)