题解 | #合并两个有序的数组#(计算合并后长度,从后往前赋值,空间复杂度O(1))

合并两个有序的数组

http://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665

1.声明一个额外空间。 空间复杂度O(n)

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        vector<int> c(m+n);
        int i = 0, j = 0, k = 0;
        while(i < m && j < n){
            if(A[i] < B[j])c[k++] = A[i++];
            else c[k++] = B[j++];
        }

        while(i < m)c[k++] = A[i++];
        while(j < n)c[k++] = B[j++];

        i = 0;

        for(int x : c){
            A[i++] = x;
        }

    }
};
  1. 一个已知数组从后往前开始赋值,空间复杂度为O(1) 且代码短
class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
       int i = m - 1, j = n -1, k = m + n - 1;
       while (i >= 0 && j >= 0){
           A[k--] = A[i] > B[j] ? A[i--] : B[j--];
       }
       while(j >= 0) A[k--] = B[j--];
    }
};
全部评论

相关推荐

序&nbsp;朋友们,好久不见。&nbsp;笔者在过去消失的五个月里被困在情绪牢笼中过的相当煎熬,一度丢失自己,觉得整个世界都是昏暗的。&nbsp;庆幸的是靠着自己纯硬扛也是走出来了。表达欲再度回归,所以真的很开心还有机会能在再和大家见面。&nbsp;破碎秋招&nbsp;抑郁情绪的引爆点必然是秋招期间遭受的打击了,从去年九月份腾讯转正被告知失败之后就开始疯狂投递简历,每天都在经历:简历挂、一面挂、二面挂、三面挂、HR面挂,每天睁开眼就被无所适从的挫败感包围。&nbsp;秋招的特点是即便流程走到最后一步也不一定会&nbsp;offer,因为还需要进入大池子进行横向对比,俗称泡池子,而这一泡我的大多数面试流程到后面就没了后文,这一度让我感觉非常绝望。我深知自己学历并...
SoNiC_X:我已经工作快2年了,当时高考没考好没去到想去的学校,觉得天要塌了;校招找不到工作,觉得天要塌了;现在工作觉得看不到未来,觉得天要塌了;最近最大的感悟就是:天会一直塌,但是生活也会一直继续下去,还是要调整好自己的心态,不要因为一时的困难把自己困住,要记住完蛋的日子永远在后头
点赞 评论 收藏
分享
虚闻松声:扫一眼,Java not java CET4 拿掉 专业技能里面可以加粗几个自己特别熟悉的。 所有的时间,最后右对齐 当然这些其实都不太重要。。。 刷题,投简历,就行了。 免费修改简历,欢迎私聊交流。
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务