看板Oversea_Job
标 题Re: [北美] Microsoft questions
发信站批踢踢参 (Sun Dec 16 01:37:02 2007)
转信站ptt!Group.NCTU!grouppost!Group.NCTU!ptt3
※ 引述《[email protected] (@Seattle)》之铭言：
: ※ 引述《[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)的一个解答了
我没有写的很清楚 不过这个题目有个隐含的事实 就是:
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