两个有序数组的合并（不创建新的数组）时间复杂度O(n)

清疚 2022-02-21 11:21 100阅读 0赞

**题目：**

给定两个有序数组a\[m\],b\[n\],要求将这两个数组合并陈一个数组，时间复杂度最大为O(n)，辅助空间为O(1)

**分析：**

设sum控制合并后的数组，a1控制合并前a数组，b1控制合并前b数组，sum，a1，b1都是从最后一位开始的（这句不理解的话直接看代码）

这个题用传统的归并排序的话不符合要求，所以要换种方法，所以：

可以将a数组扩展成m+n的长度，然后从a，b地最后一个开始比较，如果a\[a1\]>b\[b1\],那么将a\[a1\] 移动至合并后的a数组的最后一位，a1--,否则将b\[b1\]交换至合并后的a数组的最后一位，b1--;最后如果b有剩余的话，将其平移至a数组中

**代码如下：**

#include <bits/stdc++.h>
    using namespace std;
    
    void Merge_sort(int *a,int *b,int m,int n){
        int sum = m+n-1;
        int a1 = m-1;
        int b1 = n-1;
        while(a1 >= 0 && b1 >= 0){
            if(a[a1] > b[b1]){
                a[sum] = a[a1];
                a1--;
            }
            else{
                a[sum] = b[b1];
                b1--;
            }
            sum--;
        }
        while( b1 >= 0){
            a[sum--] = b[b1--];
        }
    }
    int main(){
        int m,n;
        cin >> m >> n;
        int *a,b[n];
        a = (int *)calloc(sizeof(int),(m+n));
        for(int i = 0; i < m; i++)
            cin >> a[i];
        for(int i = 0; i < n; i++)
            cin >> b[i];
        for(int i = 0; i < m+n; i++)
            cout << a[i];
        cout << endl;
        //a = (int *)realloc(a,sizeof(int)*(m+n));
        Merge_sort(a,b,m,n);
        for(int i = 0; i < m+n; i++){
            cout << a[i] << " ";
        }
    }