LeetCode 88. Merge Sorted Array

题目

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.

分析

合并有序数组

  • 输入:两个有序数组
  • 任务:合并两个有序数组,新数组仍然有序
  • 条件:合并到第一个数组
  • 输出:新有序数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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.
"""
while m > 0 and n > 0:
if nums1[m-1] >= nums2[n-1]:
nums1[m+n-1] = nums1[m-1]
m -= 1
else:
nums1[m+n-1] = nums2[n-1]
n -= 1
if n > 0:
nums1[:n] = nums2[:n]

点评

同时对两个数组从大到小进行遍历,每次遍历时,比较当前两个数组的值大小,将大的数移到新数组最后,知道有一个数组遍历完了,然后将剩余的数组添加到新数组的开始。