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

|

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

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

题目分析

给你两个有序整数数组 nums1nums2,其中 nums1 的长度为 m 加上 nums2 的长度,nums2 的长度为 nnums1 的后 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/ ↩︎