leetcode-88. 合并两个有序数组

题面

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。

样例

1. 输入:

nums1 = [1,2,3,0,0,0], m = 3

nums2 = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

2. 输入:

nums1 = [0], m = 0

nums2 = [6], n = 1

输出: [6]

算法

时间复杂度：O(n+m)

与合并有序链表类似。

1. 如果m为0，直接返回就可以了。如果n为0,则需要把nums2中前n个元素都搬到nums1中，返回。

2. 如果，m、n都不为0，计算合并后的元素数len = m+n, 我们从后往前为nums1[len--]赋max(nums1[m]nums2[n]), 之后较大的数组下标自减（已经比较后填入了nums1中），直到某个数组被遍历完。

3. 如果2之后，m == 0,那么代表nums1中的元素都已经填完了，就把nums2中剩下的元素按次序填入nums1中即可；如果 n == 0，即nums2填完了，那就结束，剩下的nums1本来就是有序的。

源码

 class Solution {

 public:

     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

         if(n == )

             return ;

         else if(m == )

         {

             for(int i=; i<n; i++)

                 nums1[i] = nums2[i];

         }

         //从往前放置

         int len = m+n-;

         m--; n--;

         while(m >=  && n >=  && len >= )

         {

             if(nums1[m] < nums2[n])

             {

                 nums1[len] = nums2[n];

                 len--; n--;

             }

             else

             {

                 nums1[len] = nums1[m];

                 len--; m--;

             }

         }

         if(m < )

         {

             for(int i=; i<=n; i++)

                 nums1[i] = nums2[i];

         }

     }

 };

巴特西

leetcode-88. 合并两个有序数组 · Aaray

最新文章

热门文章