Merge sorted array

DocumentsAlgorithms
Algorithms, Leetcode, Python
Catalogue
  1. 1. Question
  2. 2. 思路
  3. 3. Code

Question

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

思路

由于两个数组都已经排序，因此可以从后往前比较两个数组，将较大的元素插入未排序的部分。若数组1先排完，则说明数组2的剩余元素均比数组1小，所以将剩余部分填充完即可；若数组2先排完，则说明数组1剩余元素均小于数组2，由于合并是在数组1上原地完成，因此不需要再操作。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    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.
        """
        end = m+n-1
        m -= 1
        n -= 1
        while end >= 0 and m >= 0 and n >= 0:
            if nums1[m] > nums2[n]:
                nums1[end] = nums1[m]
                m -= 1
            else:
                nums1[end] = nums2[n]
                n -= 1
            end -= 1
        while n >= 0:
            nums1[end] = nums2[n]
            n -= 1
            end -= 1
Comments