Day 4：88. Merge Sorted Array

今日题目

题目连结：88. Merge Sorted Array
题目主题：Array、Two Pointer、Sorting

今天要说说另一种排序法，这次选的题目个人觉得是很典型的 Insertion Sort 的例子，非常适合来练习这个排序法。

简单说说 Insertion Sort

Insertion Sort是一种基本的排序方法，用一个双回圈处理排序的方法。以小到大的排序为例，Insertion Sort的每一圈都会往後走一步将前面的数字确认好排序，走到最後一个数字就能排好这个阵列的顺序，处理的过程如下图。

范例：nums = [32, 2, 18, 45, 15]

红方框是每一圈处理的范围，红色数字是主要处理的值，这个值会一直往前去比对是否比较小，如果比较小就跟前面的数字换，图中每一圈上方的黑色箭头就是这个红色数字走的过程，这个数字会一直走到前面的数字比较小才停下来，就像第五圈 15 的状况，走了三步後因为2比较小，所以停在这。当然也有像第四圈的状况，连走都不用走，45就刚好是这个范围最大的值，所以不用动。

题目解説

建议可以看看LeetCode原本的题目说明，这边是用我的方式说明题目，参考就好。

本题目标是合并两个数字阵列，并且将这个阵列做好正排序。而这两个阵列分别为nums1, nums2，另外还会给 m 跟 n 这两个值。

nums1 跟 nums2 再输入时已经是正排序好的阵列
m+n 代表 nums1 的总长度
m 代表 nums1 中有数字的长度
n 代表 nums2 的长度

nums1 阵列中前 m 个元素皆为整数值，後 n 个元素为0来表示，这n个0不需被排进最终合并结果。

最後要注意的是，这个最终的输出不会由方法的return回传，而是修改到nums1阵列中来代表完成。

约束：

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

范例1

输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
解释: 可以看到输出结果是[1,2,2,3,5,6]，nums1的0都被nums2的数字[2,5,6]取代後正排序後的结果。

范例2

输入: nums1 = [1], m = 1, nums2 = [], n = 0
输出: [1]
解释: 如果 nums2 是空的，合并结果其实就是 nums1 本身，所以直接输出[1]。

范例3

输入: nums1 = [0], m = 0, nums2 = [1], n = 1
输出: [1]
解释: m 如果是 0 代表 nums1 没有任何数字，nums1 有 0 是因为n有值，所以会补上这个0，应直接忽略这个0。因此合并後的结果就是 nums2 的所有值直接取代放进 nums1，最後输出[1]。

建议到这边先停下来，尝试自己解解看，若没有想法可再继续走下去。

解题的想像

文字描述

1. 排除 n = 0 的状况，不需处理直接结束。
2. 排除 m = 0 的状况，只需要将nums2中的值取代到nums1中对应的位置即可结束。
3. 跑一个双回圈
   • 第一层每一圈处理一个数字，将nums2的数字取代进nums1中对应的位置。
   • 第二层回圈，将nums1新进来的数字跟前面的数字做排序。

图解过程

范例：nums1 = [1, 2, 3, 0, 0, 0] , m = 3 , nums2 = [2, 5, 6] , n = 3

上图中，红色方框是每一圈处理范围，每一圈都会从nums2把一个数字取代到nums1对应的位置，订好它的位置以後会变绿色数字，而黑色箭头就是红色数字走的过程。最终上图中输出的部份，绿色的数字就是从nums2移动过来的数字。

其实过程跟Insertion Sort处理过程有90%像，只是每一次处理的目标数字是从另外一个阵列过来的数字，其余过程都一样。

若因为没想法而走到这边，建议看完想像以後再给自己一次机会试一次。

程序码撰写

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 忽略 n = 0 的状况，因为nums1直接是完整的
        if n <= 0: return
        # m = 0 的状况，要将nums2的值都取代近nums1中
        if m <= 0: 
            nums1[:] = nums2
            return
        # 这是Insertion Sort满典型的样子
        # 但过程是nums2的值插进nums1中来做排序
        for startIdx in range(m, m+n):
            nums1[startIdx] = nums2[startIdx-m]
            for idx in range(startIdx, 0, -1):
                if nums1[idx] >= nums1[idx-1]:
                    break
                tmp = nums1[idx]
                nums1[idx] = nums1[idx-1]
                nums1[idx-1] = tmp

希望您今天能了解到...

• Insertion Sort 基本概念
• 88. Merge Sorted Array 解题方法

若内容有什麽问题或建议欢迎一起交流：）
感谢您今天愿意花时间看完这篇文章~~~~

Next：20. Valid Parentheses