Re: [北美] Microsoft questions
※ 引述《HYL.bbs@ptt.cc (@Seattle)》之銘言：
: ※ 引述《LINC.bbs@ptt3.cc (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)的一個解答了
我沒有寫的很清楚 不過這個題目有個隱含的事實 就是:
a[]的長度 >= # elements in a[] + # elements in b[]
在我的例子裡, a[]的長度為10, 但是一共只有8個elements(5 in a[], 3 in b[])
所以你的code裡要修改一下 i 就會沒問題
--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 151.199.225.228
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：
Oversea_Job 近期熱門文章
PTT職涯區 即時熱門文章
