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

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例:

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

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

A.length == n + m

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sorted-merge-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：
  • 双指针， m和n分别指向数组A 和 B的末尾

  • 从后往前开始比较，较大者放入m + n - 1的位置

  • 并将较大者的指针往前移动一位

  • 直到m 和 n 两个指针都移动到末尾

  • 当m为0，且n不为0时，说明元素已经全部合并的A中，直接break

  • 当n为0，且m不为0时，说明A中的元素已全部合并，则依次把B中的元素合并到A中

  • 排序后的数组放入A中，因为A的存储空间时足够的

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

  • 空间复杂度: O(1)

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public void merge(int[] A, int m, int[] B, int n) {
        while (m > 0 || n > 0){
            if (m == 0){
                A[n - 1] = B[n - 1];
                n --;
                continue;
            }

            if (n == 0){
                break;
            }

            int a = A[m - 1];
            int b = B[n - 1];

            if (a > b){
                A[m + n - 1] = a;
                m --;
            }else {
                A[m + n - 1] = b;
                n --;
            }
        }
    }