题干:

给你两个**有序整数数组** nums1nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组

说明:

初始化 nums1nums2 的元素数量分别为 mn
你可以假设 nums1 有足够的空间空间大小大于或等于 m + n)来保存 nums2 中的元素。

示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

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

读题:

这题的条件很明确:

  • 给出的已经是有序的两个数组
  • nums1 的长度 >= m+n

做了几道题下来,发现数组的操作无外乎就是合并,排序,但是想的挺简单的,做起来却又觉得没那么简单。

解决思路:

最简单粗暴的方法:

使用 System.arraycopy nums2 放入 num1 中,然后调用 Arrays.sort API 进行排序。

但是这样做的话相当于重新排序了一遍,效率很低,而且这也不符合这个考题的初衷。

我的想法是:遍历nums2nums1 中对比,如果小于当前索引的元素则将该元素置于该索引处,同时 nums1 的所有元素索引+1

但是想的挺清楚的,做的时候又有点迷糊,觉得不太对。

后来翻评论区,看到一个写的很简洁执行速度又很快的代码,感觉实现的很好,搬运在这里:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }
        
        // 将 Nums2 中 小于 nums1 的元素赋值到 nums1 数组中
        while (n >= 0) {
            nums1[p--] = nums2[n--];
        }
    }

然后我开始理解这段代码:这段代码使用了 **双指针倒序比较赋值**的方法

  • 首先,这里定义了一个变量p,其值为 nums1 的长度m + nums2 的长度n -1 ,该位置其实就是 nums1 的尾部,所以 这个指针指向 第一个数组的最后一个元素。 ,并且此时 m 和 n 也都做了一次递减。
  • 开始对 nums1 和 nums2 进行 自旋 ,并且从 nums1 的尾部开始,对比 nums1[m] 处 与 nums2[n] 处的元素大小关系,将 nums1 的尾部赋值给 较大的那个。因为已知 nums1 的尾部 会是0,其个数与 nums2的 元素数量即 n 的大小一致, 所以从尾部开始赋值这个想法很精巧。
  • 最后将 nums2 中比 nums1 小的元素赋值到 nums1 中

IMG_D31542004F8E-1

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

最是人间留不住,曾是惊鸿照影来。