※ 引述《[email protected] (Go cubs!)》之銘言：
: Given 2 sorted arrays, a[] and b[]
: combine them with no extra array(or linear space).
: e.g.: a[10] = [1, 3, 5, 7, 9]
: b[3] = [2, 4, 6]
: the result is a[] = [1, 2, 3, 4, 5, 6, 7, 9], assuming a[] has enough space.
: Can anyone solve it? I don't see a good solution(meaning O(N)) yet.
反過來走如何？
int apos = 4;
int bpos = 2;
for(int i = a.length -1 ; i >= 0 ; i--){
if(apos < 0){
a[i] = b[bpos];
bpos --;
}else if(bpos <0){
a[i] = a[apos];
apos --;
}else if(a[apos] >= b[bpos]){
a[i] = a[apos];
apos --;
} else {
a[i] = b[bpos];
bpos --;
}
}
試過幾個edge case都沒問題，這應該就是O(n)的一個解答了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 207.188.29.244
※ 編輯: HYL 來自: 207.188.29.244 (12/15 06:50)