作者poc7667 (poc)
看板C_and_CPP
标题[问题] 在2n大小的阵列中，挑出n个元素排成阵列
时间Wed Feb 25 16:58:56 2009
在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)
1F：→ windincloud:问一下 那照你这样说的说 所有的b[n] 必落在A[2*n] 02/25 17:19
2F：→ windincloud:也就是说原先已排序後A[2n+1]是不会出现在B[n]中罗~ 02/25 17:20
3F：→ windincloud:若我的想法没错的话~ 那这样就是A[] sorting问题罗~ 02/25 17:22