逆向双指针：合并两个数组

|

题目：88. 合并两个有序数组[1]

如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

给你两个有序整数数组 nums1 和 nums2，其中 nums1 的长度为 m 加上 nums2 的长度，nums2 的长度为 n。nums1 的后 n 个位置留空，以容纳 nums2。要求合并这两个有序数组，使合并后的数组仍然有序。

为了不开辟新数组，只能从后向前填充nums1，这也是解决问题的关键。

解题思路

这里可以使用逆向双指针法：

  • 指针i指向nums1数组的最后一个元素，指针j指向nums2数组的最后一个元素；
  • 另外创建一个指针k指向合并后的数组的最后一个位置的索引；
  • 对比i和j指向的元素谁的值比较大则把谁放到nums1[k]处，并移动相应的指针，直到i或者j小于0；
  • 最后如果j仍然大于等于0，意味着nums2中还有未合并的元素，把这些元素复制到nums1的开头

Java解法

下面是使用Java语言的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            // 从后向前填充nums1
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        // 处理nums2中剩余的元素
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }
}

References

  1. 88. 合并两个有序数组. Retrieved from https://leetcode.cn/problems/merge-sorted-array/ ↩︎