首页 > 代码库 > Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.The number of elements initialized in nums1and nums2 are m and n respectively.

问题:

两个有序数组,合并成一个有序数组,如果第一个数组空间足够容纳两个数组。

分析:

考虑到a数组非常大,能够直接在a数组上进行合并,可是要讲究效率。假设单纯从前往后合并。那么效率会非常低,由于a数组后面的数字须要不停的移动。换一种思路,我们採用从后往前合并,首先计算出总长度,设置一个指针从a数组最后往前移动。

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstdlib>  
  4. using namespace std;  
  5.   
  6. #define MAX 1024  
  7.   
  8. void combine(int *a, int *b, int len1, int len2)  
  9. {  
  10.     if(a == NULL || b == NULL || (len1 + len2) > MAX)  
  11.         return ;  
  12.   
  13.     int new_point;  
  14.     int a_point = len1 - 1;  
  15.     int b_point = len2 - 1;  
  16.   
  17.     new_point = len1 + len2 -1; //总的长度  
  18.   
  19.     while(a_point >= 0 && b_point >= 0)  
  20.     {  
  21.         if(a[a_point] > b[b_point])  
  22.         {  
  23.             a[new_point--] = a[a_point--];  
  24.         }  
  25.         else  
  26.         {  
  27.             a[new_point--] = b[b_point--];  
  28.         }  
  29.     }  
  30.   
  31.     while(a_point >= 0)  
  32.     {  
  33.         a[new_point--] = a[a_point--];  
  34.     }  
  35.   
  36.     while(b_point >= 0)  
  37.     {  
  38.         a[new_point--] = b[b_point--];  
  39.     }  
  40.   
  41.     return ;  
  42. }  
  43.   
  44. int main()  
  45. {  
  46.     int b[MAX] = {1,2,3,4};  
  47.     int a[MAX] = {5,6,7,8};  
  48.   
  49.     combine(a, b, 4, 4);  
  50.   
  51.     for(int i =0 ; i <= 4 + 4 -1; i++)  
  52.     {  
  53.         cout << a[i] << " ";  
  54.     }  
  55.   
  56.     return 0;  
  57. }  


C++运用STL风格:

class Solution
{
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        vector<int> result;
        vector<int>::iterator iter1=nums1.begin();
        vector<int>::iterator iter2=nums2.begin();
        while(iter1!=nums1.begin()+m && iter2!=nums2.begin()+n)
        {
            if(*iter1<=*iter2)
            {
                result.push_back(*iter1);
                ++iter1;
            }
            else
            {
                result.push_back(*iter2);
                ++iter2;
            }
        }
        while(iter1!=nums1.begin()+m)
        {
            result.push_back(*iter1);
            ++iter1;
        }
        while(iter2!=nums2.begin()+n)
        {
            result.push_back(*iter2);
            ++iter2;
        }
        nums1.swap(result);
    }
};





Merge Sorted Array