Jianbo Dai's

lc088.合并两个有序数组

 
  • Apr 26, 2020

合并两个有序数组

再做一个可以用双指针法做的题，将两个数组的值都合并到第一个数组里面去，注意到其实这就是归并排序。解法如下，分别用两个指针指向两个数组非零数 的末尾, 再用另一个指针t指向数组1的最末尾，然后比较这两个数的大小并将比较大的数存到第一个t指针所指的位置，存储后将t也往前移动一位。注意我们 不能从前往后移动，因为t指针所指的位置会将未处理的数组1中的数字给覆盖掉。随着三个指针的移动，合并也相应完成了，但是注意到，由于判定条件是两个 指针都不能越界，故数组1中都指针指向数组最开始时会停下，但此时数组2中的数字并未全被加入数组1中（由于数组2中遗留的数字比数组1中在数组开头的第 一个数字还小的缘故），我们要做进一步的处理即将数组2中剩余的数字复制到数组1最开头。另外，这种操作不需要对数组1进行，是因为我们在将所有数字都 合并到数组1当中，当指向数组2中都指针指向最开始时而导致循环停止时，数组1剩下都数字自然已经符合了题目都要求。

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        t = m + n
        while n >= 1 and m >= 1:
            if nums1[m-1] >= nums2[n-1]:
                nums1[t-1] = nums1[m-1]
                m -= 1
                t -= 1
            else:
                nums1[t-1] = nums2[n-1]
                n -= 1
                t -= 1
        while n >= 1:
            nums1[t-1] = nums2[n-1]
            t -= 1
            n -= 1
        return nums1
Search