[LeetCode]88. 合并两个有序数组

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

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

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

思路:

这是一道简单难度的题目。最简单的思路是直接把小一些的vector<int> 的元素附到空间足够的大vector<int>中，然后直接调用sort完事。这样做不本质，并起不到什么训练技能的效果，所以应当去手写一个遍历法排序。

具体怎么做呢？容易想到双指针遍历的方法：对于一个m长度的数组nums1和n长度的nums2，建立一个m+n长的临时数组保存已有序的部分序列TempResult，维护index1和index2两个指针。当nums1[index1] > nums2[index2]的时候，把nums2[index2]附加到TempResult后面并index2自增1，反之附加nums1[index1]并index1自增1，当两个数组均遍历完时TempResult即为有序递增数组了。赋值给nums1即可。

LeetCode有个从大到小将nums2元素反向置入nums1的Java版答案，非常机智地利用两个链表已经有序而避开了需要建立临时数组的问题，我改写了一个C++版本。

AC代码:

//偷懒而缓慢的STL排序法
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int cursor_nums1 = m;
        for(vector<int>::iterator iter2 = nums2.begin(); iter2 != nums2.end(); iter2++)
        {
            nums1[cursor_nums1] = *iter2;
            cursor_nums1++;
        }
        sort(nums1.begin(),nums1.end(),less<int>());
    }
};

//要块一些的双指针遍历法
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(n == 0)
            return;
        if(m == 0)
        {
            nums1 = nums2;
            return;
        }
        vector<int> TEMPRESULT;
        int index1 = 0, index2 = 0;
        for(;(index1 < m) && (index2 < n);)
        {
            if(nums1[index1] > nums2[index2])
            {
                TEMPRESULT.push_back(nums2[index2]);
                index2++;
            }
            else
            {
                TEMPRESULT.push_back(nums1[index1]);
                index1++;
            }
        }
        if(index1 < m)
        {
            while(index1 < m)
            {
                TEMPRESULT.push_back(nums1[index1]);
                index1++;
            }
        }
        if(index2 < n)
        {
            while(index2 < n)
            {
                TEMPRESULT.push_back(nums2[index2]);
                index2++;
            }
        }
        nums1 = TEMPRESULT;
    }
};

//由云澈的Java代码改编而来的C++版本
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(n == 0)
            return;
        if(m == 0)
        {
            nums1 = nums2;
            return;
        }
        int length = m-- + n-- -1;
        for(;m >= 0 && n >= 0;)
        {
            if(nums1[m] > nums2[n])
            {
                nums1[length] = nums1[m];
                m--;
            }
            else
            {
                nums1[length] = nums2[n];
                n--;
            }
            length--;
        }
        while(n >= 0)
        {
            nums1[length] = nums2[n];
            n--;
            length--;
        }
    }
};

[LeetCode]88. 合并两个有序数组

Published by

WiiGe