「刷刷刷」88.合并两个有序数组

发表于 更新于 分类于

题目

难度：简单

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array

思路

审题：数组为从小到大排列，数组1的末尾留有足够空位。

将数组2合并入数组1，如果我们从后往前（从大到小）遍历两个数组比较，将大值从数组1末尾依次向前填入，则可以不需要额外的空间临时存储数组1的元素。

所以：双指针指向两个数组最大的元素，依次比较大小，将较大值放入数组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
25
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        // 指向数组1末尾位置，也就是下一个要插入的元素的位置的指针
        int length = m + n - 1;
        
        // 指向数组1数组2各自末尾元素指针
        int j = m - 1, k = n - 1;

        // 遍历比较，将较大值从后往前插入数组1
        while (j >= 0 && k >= 0) {  //   1️⃣
            if (nums1[j] > nums2[k]) {  // 2️⃣
                nums1[length--] = nums1[j--];
            } else {
                nums1[length--] = nums2[k--];
            }
        }
        
        // 3️⃣
        while (k >= 0) {
            nums1[length--] = nums2[k--];
        }
    }
}

需要注意的细节是：

  • 1️⃣：注意这里循环条件是 j 和 k 都大于等于 0
    • 如果数组2先扫描完（k=0），那数组1剩余元素不需要再动了
    • 如果数组1先扫描完（j=0），则跳到3️⃣
  • 2️⃣：如果两个元素相等，优先插入数组2的元素，避免额外的插入
  • 3️⃣：如果是数组1的元素先扫描完，则需要把数组2剩余的元素依次插入

作者：prik
永久链接： https://trzoey.github.io/blog-prik/algorithmic/88.合并两个有序数组/
转载请注明出处，谢谢合作💓。