面试题10.01合并两个有序数组

题目描述 (opens new window)

TIP

标签: 数组、双指针、排序

算法思路

方法一: 直接合并后排序

最直观的方法就是先将数组B放进数组A的尾部，然后直接对整个数组进行排序。

var merge = function(A, m, B, n) {
  // splice
  A.splice(m, A.length - m, ...B);
  A.sort((a, b) => a - b);
};

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        for (int i = 0; i != n; ++i) {
            A[m + i] = B[i];
        }
        Arrays.sort(A);
    }
}

方法二: 双指针

方法一没有利用数组A和数组B已经排序的性质，所以阅读题目特别重要。为了利用这个性质，我们可以使用双指针的方法，这个方法将两个数组看成队列，每次从两个数组头部取出比较小的数字放在结果中。

var merge = function(A, m, B, n) {
  // 两个指针 初始化指向数组的头部 pointer
  let pa = 0, pb = 0;
  // 声明一个 m+n 的空间大小的数组
  const sorted = new Array(m + n).fill(0);
  // 当前的指针的位置
  var cur;

  // 只要其中一个数组没有遍历完毕，就要一直进行循环
  while (pa < m || pb < n) {
    if (pa === m) {
      // 这里使用的是后自增 
      // cur = B[pb]
      // pb++ // pb = pb + 1 
      cur = B[pb++];
    } else if (pb === n) {
      cur = A[pa++];
    } else if (A[pa] < B[pb]) {
      cur = A[pa++];
    } else {
      cur = B[pb++];
    }
    sorted[pa + pb - 1] = cur;
  }
  for (let i = 0; i != m + n; ++i) {
    A[i] = sorted[i];
  }
};