首页 > 代码库 > leetcode[89] Merge Sorted Array

leetcode[89] Merge Sorted Array

合并两个有序数组,放在A中,A中的空间足够。

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 (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m andn respectively.

从后往前放,比较A和B的从后往前的,比较大的放在m+n-1的位置。然后一直减减。

class Solution {public:    void merge(int A[], int m, int B[], int n)     {while(m > 0 && n > 0)        {            if (A[m-1] > B[n-1])            {                A[m+n-1] = A[m-1];                m--;            }            else            {                A[m+n-1] = B[n-1];                n--;            }        }        if (m == 0)            while(n > 0)             {                A[n-1] = B[n-1];                n--;            }        return ;    }};

 也可以写短一点:

class Solution {public:    void merge(int A[], int m, int B[], int n)     {        int nowA = m - 1, nowB = n - 1, last = n + m - 1;        while(nowA >= 0 && nowB >=0)        {            A[last--] = A[nowA] > B[nowB] ? A[nowA--] : B[nowB--];        }        while(nowB >= 0)            A[last--] = B[nowB--];        return ;    }};

 

leetcode[89] Merge Sorted Array