leetCode-88:Merge Sorted Array

问题描述

给定两个有序数组 nums1 和 nums2，其中 nums1 的有效数字个数为 m， nums2 的有效数字个数为 n，nums1 的长度大小为 m + n，即 nums1 数组能存放 nums1 和 nums2 的所有有效数字。要求将数组 nums2 合并到 nums1 上，并且合并后的数组保持有序。题目链接：**点我**

样例输入输出

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

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

输入：nums1 = [1], m = 1, nums2 = [], n = 0

输出：[1]

问题解法

此题最简单的做法是把 nums2 的元素直接补到 nums1 后面，然后直接调用 Arrays.sort 对 nums1 进行排序。但是这样时间复杂度为 O(nlogn)，同时也没利用上数组有序的特点。因此可以考虑归并排序的做法，为了避免不停的挪动数组，可以从数组的末尾往前逐渐比较放置元素。代码如下

class Solution
{
    public void merge(int[] nums1, int m, int[] nums2, int n)
    {
        int first = m - 1;
        int second = n - 1;
        for (int i = m + n - 1; i >= 0; i--)
        {
            if (first >= 0 && second >= 0)
            {
                if (nums1[first] > nums2[second])
                {
                    nums1[i] = nums1[first];
                    first--;
                }
                else
                {
                    nums1[i] = nums2[second];
                    second--;
                }
            }
            else
            {
                if (first >= 0)
                {
                    nums1[i] = nums1[first];
                    first--;
                }
                else
                {
                    nums1[i] = nums2[second];
                    second--;
                }
            }
        }
    }
}