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

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

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

题目大意 #

给定两个排序后的数组 AB,以及 A 的元素数量 mB 的元素数量 nA 的末端有足够的缓冲空间容纳 B。 要求:编写一个方法,将 B 合并入 A 并排序。

解题思路 #

双指针,归并排序。

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

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]
本站总访问量  次  |  您是本站第  位访问者