跳至主要內容

面试题 10.01. 合并排序的数组

ITCharge大约 1 分钟

面试题 10.01. 合并排序的数组open in new window

  • 标签:数组、双指针、排序
  • 难度:简单

题目链接

题目大意

描述:给定两个排序后的数组 AB,以及 A 的元素数量 mB 的元素数量 nA 的末端有足够的缓冲空间容纳 B

要求:编写一个方法,将 B 合并入 A 并排序。

说明

  • A.length==n+mA.length == n + m

示例

  • 示例 1:
输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

解题思路

思路 1:归并排序

可以利用归并排序算法的归并步骤思路。

  1. 使用两个指针分别表示AB 正在处理的元素下标。
  2. AB 进行归并操作,将结果存入新数组中。归并之后,再将所有元素赋值到数组 A 中。

思路 1:代码

class Solution:
    def merge(self, A: List[int], m: int, B: List[int], n: int) -> None:
        """
        Do not return anything, modify A in-place instead.
        """
        arr = []
        index_A, index_B = 0, 0
        while index_A < m and index_B < n:
            if A[index_A] <= B[index_B]:
                arr.append(A[index_A])
                index_A += 1
            else:
                arr.append(B[index_B])
                index_B += 1
        while index_A < m:
            arr.append(A[index_A])
            index_A += 1
        while index_B < n:
            arr.append(B[index_B])
            index_B += 1
        for i in range(m + n):
            A[i] = arr[i]

思路 1:复杂度分析

  • 时间复杂度O(m+n)O(m + n)
  • 空间复杂度O(m+n)O(m + n)