推 duer:O(5+3) is still O(N) <-- I think that's the solution 12/15 05:53
> -------------------------------------------------------------------------- <
發信人: Yuheng.bbs@ptt3.cc (宇恆), 看板: Oversea_Job
標 題: Re: [北美] Microsoft questions
發信站: 批踢踢參 (Sat Dec 15 04:22:30 2007)
轉信站: ptt!Group.NCTU!grouppost!Group.NCTU!ptt3
※ 引述《LINC (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.
If "a[] has enough space" means a[] can store a + b,
then right shift a by size(b), and take a[0] as the
begining of storing new value.
You are welcome to correct me if there is any error.
^^
--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 168.7.230.23
> -------------------------------------------------------------------------- <
作者: HYL (@Seattle) 看板: Oversea_Job
標題: Re: [北美] Microsoft questions
時間: Sat Dec 15 06:47:16 2007
※ 引述《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)的一個解答了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 207.188.29.244
※ 編輯: HYL 來自: 207.188.29.244 (12/15 06:50)
> -------------------------------------------------------------------------- <
發信人: LINC.bbs@ptt3.cc (Go cubs!), 看板: Oversea_Job
標 題: Re: [北美] Microsoft questions
發信站: 批踢踢參 (Sun Dec 16 01:37:02 2007)
轉信站: ptt!Group.NCTU!grouppost!Group.NCTU!ptt3
※ 引述《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
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.
--
※ 發信站: 批踢踢參(ptt3.cc)
◆ From: 70.20.254.187