题目描述

Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

题目大意

给定两个排序的整型数组A和B，将B合并到A中。

假设A有足够的空间来容纳B中的元素，A和B中初始的元素数目分别为m和n。

思路

最优解：从后往前处理,不需要开辟额外空间。
i从A的末尾，j从B末尾开始，两两比较，大的放在末端。
如此类推如果A穷尽，把B元素依次放进A的前几个位置（第二个while循环），如果B穷尽，正好结束（此时不用判断）。

代码

#include<iostream>
using namespace std;

void merge(int A[], int m, int B[], int n)
{
    int i = m-1, j = n-1, index = m+n-1;
    
    // 当A和B都没有遍历完
    while(i>=0 && j>=0)
    {
        // 大的放到当前index位置
        A[index--] = A[i]>B[j] ? A[i--]:B[j--];
    }
    
    // 当B没有遍历结束时，直接把B剩余元素放进A
    // A未穷尽时不用判断，直接就在前边了
    while(j >= 0)
    {
        A[index--] = B[j--];
    }
}

int main()
{
    int A[10] = {1, 3, 5, 7, 9};
    int B[] = {2, 4, 6, 8, 10};
    
    merge(A, 5, B, 5);
    
    for(int i=0; i<10; i++)
    {
        cout<<A[i]<<' ';
    }
    
    cout<<endl;
    
    return 0;
}

运行结果

以上。