LeetCode--88

一、题目

有两个排序的整数数组，分别是数组1和数组2，将数组2合并到数组1中，合并以后的数组1，仍是有序数组。

提示：

• 数组1有m个元素，数组2有n个元素
• 可以假设数组1有足够的空间（大于m+n）去容纳从数组2得到的额外的元素。

具体化问题，写出两个有序数组以后，分析问题得出思路。以所给例子作为参考。

二、思路

思路1：

从前往后构造数组，拿array2中的最前面的元素跟array1中的最前面的元素比较，找到正确的排序 以后插入，然后把array1后面的元素都向后移一位。
时间复杂度太高。

思路2：

新构造一个空数组array3，那array2中的最前面的元素跟array1中的最前面的元素比较，然后将小的数依次插入到array3后面。
这个方法降低了时间复杂度，但是额外构造了一个数组。

一般这种合并有序的序列，思路应该都是从后向前合并。

##############################################################

思路3：

提示中已经给出，假设array1有足够的空间了，于是我们不需要额外构造一个数组，并且可以从后面不断地比较元素进行合并。

• 比较array2与array1中最后面的那个元素，把最大的插入第m+n位
• 改变数组的索引，再次进行上面的比较，把最大的元素插入到array1中的第m+n-1位。
• 循环一直到结束。循环结束条件：当index1或index2有一个小于0时，此时就可以结束循环了。如果index2小于0，说明目的达到了。如果index1小于0，就把array2中剩下的前面的元素都复制到array1中去就行。

功能代码：
输入一次m>n的情况
输入一次m<n的情况

特殊输入情况：

• 当array1为空，array2不为空时，将array2的所有元素添加到array1中即可
• 当array1不为空，array2为空时，就是上面的循环结束条件，直接返回array1.
• 当array1跟array2都为空时，返回空。

我们发现利用index1和index2来做判断以后，实现功能代码的情况下，就能自动满足特殊输入情况了。

class Solution:
    def merge(self, nums1, m, nums2, n):
        """
        :type nums1: List[int]
        :type m: int
        :type nums2: List[int]
        :type n: int
        :rtype: void Do not return anything, modify nums1 in-place instead.
        """
        
        index1 = m - 1
        index2 = n - 1
        #nums1的长度是m+n
        while index2 >= 0:
            if index1 < 0:
                #注意，如果m为0，那么此时index1已经为-1了。执行完下一步就可以跳出循环了。
                #需要break
                nums1[0:index2+1] = nums2[0:index2+1]
                break
                
            if nums1[index1] >= nums2[index2]:
                nums1[index1 + index2 + 1] = nums1[index1]
                index1 -= 1
            else:
                nums1[index1 + index2 + 1] = nums2[index2]
                index2 -= 1