推 ykjiang:如果每個元素都會用到，這個方法一樣是 O(N) 11/17 11:28
※ 引述《jeunder ()》之銘言：
: 請教大家一個問題.
: 有一個陣列 x[2N] 要將其內容根據某個排列規則做 permutation.
: 規則如下:
: 就是將 x 的偶數項依序放到 x[0 ~ N-1],
: 將 x 的奇數項依序放到 x[N ~ 2N-1].
: 希望能夠做到時間複雜度為 O(N), 這顯然很容易辦到.
: 但是我又希望空間複雜度能夠是 O(1), 也就是不可以有隨 N 而變大的暫存變數.
: 這是否有可能辦到?
: 感覺上似乎和離散數學裡面的 permutation group 有關?
: 想請教大家的想法. 謝謝. :)
我不會離散數學 T___T
不過，在存取陣列的時候多包一層就啥事情都沒了
class foo{
private int x[] = new int[2*n];
//普通的取得 element
public int getElement(int i){
return x[i]
}
//特別的取得 element
public int getPermutationElement(int i){
if(i>n){ //奇數
return x[(i-n)*2+1];
}else{
return x[i*2];
}
}
}
=====
There is no spoon...
--
侃侃長論鮮窒礙 網站：http://www.psmonkey.idv.tw
眾目睽睽無心顫 個人版：telnet://legend.twbbs.org
煢居少聊常人事
殺頭容易告白難 歡迎參觀 Java 版（@ptt.cc）精華區 \囧/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.199.201