Microsoft questions - 海外工作

※ 引述《[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)的一個解答了

--