美文网首页
写一个函数,合并两个有序数组

写一个函数,合并两个有序数组

作者: XYZ7 | 来源:发表于2017-03-03 22:14 被阅读0次
  1. 思路
    当一个数组的空间足够大时可以将两个有序数组从后向前排序以提升效率。

2.代码

#include <iostream>

#define N 100                //数组的最大长度

using namespace std;

int main(int argc, const char * argv[]) {
    
    //假设两个数组中有一个数组的空间足够大到容纳两个数组,因此可以将两个数组合并到这个空间足够大的数组中,这里选择a1
    int a1[N] = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19};
    int a2[N] = {2, 4, 6, 8, 10, 12, 14, 16, 18};
    int len1 = 10;
    int len2 = 9;
    
    //从后向前比较,初始化两个数组当前比较位置的下表和当前插入位置的下标
    int cur1 = len1 - 1;
    int cur2 = len2 - 1;
    int cur3 = len1 + len2 - 1;
    
    //当两个数组都同时还有元素未必较完时
    while(cur1 >= 0 && cur2 >= 0) {
        if(a1[cur1] > a2[cur2]) {
            a1[cur3] = a1[cur1];
            cur1--;
        }
        else {
            a1[cur3] = a2[cur2];
            cur2--;
        }
        cur3--;
    }
    
    //当a1数组有剩余元素没比较时无需移动,因为已到它的最终位置
    //当a2数组有剩余元素没比较时直接将剩下的元素拷贝到a1数组的前端
    if(cur2 >= 0) {
        while( cur2 >= 0 ) {
            a1[cur2] = a2[cur2];
            cur2--;
        }
    }
    
    for(int i = 0;i < len1 + len2;i++)
        cout<<a1[i]<<" ";
    
    return 0;
}

相关文章

  • 数据结构-Java 02.习题汇总1

    1. 合并两个有序的数组 给出两个有序的整数数组A和B,请将数组B合并到数组A中,变成一个有序的数组。注意:可以假...

  • 合并两个有序数组(C)

    合并两个有序数组,合并完之后仍有序:

  • 有序数组合并

    1、两个有序数组合并(产生新数组) 2、两个有序数组合并(返回原来某个数组)

  • 作业帮

    1、写输出,关于提升 分别输出 相当于 拓展: 2、两个有序数组,合并成一个有序数组。 思路,A,B两个数组从头比...

  • 算法 -- 归并排序 - 草稿

    merge 归并排序原理 归并排序 == 递归 + 合并 合并 将两个有序的数组合并成一个有序的大数组;(从两个小...

  • 4. 寻找两个有序数组的中位数

    分析 已知两个有序数组,找到两个数组合并后的中位数。 解法一 简单粗暴,先将两个数组合并,两个有序数组的合并也是归...

  • LeetCode-88-合并两个有序数组

    LeetCode-88-合并两个有序数组 88. 合并两个有序数组[https://leetcode-cn.com...

  • js 合并两个有序数组 成一个有序数组

    将两个有序数组合并成一个有序数组,假设两个数组,a和b合并成c. 我的想法是,以b数组作为参照,从下标0 开始 逐...

  • 2个有序数组求合并后的中位数

    第一步:   假设两个有序数组(已经各自排序完成了)长度相等,试写函数找出两个数组合并后的中位数。第二步:假设两个...

  • 写一个函数,合并两个有序数组

    思路当一个数组的空间足够大时可以将两个有序数组从后向前排序以提升效率。 2.代码

网友评论

      本文标题:写一个函数,合并两个有序数组

      本文链接:https://www.haomeiwen.com/subject/rlpcgttx.html