写点什么

LeetCode 题解:88. 合并两个有序数组,双指针 + 从后往前,JavaScript,详细注释

用户头像
Lee Chen
关注
发布于: 2020 年 08 月 17 日
LeetCode题解:88. 合并两个有序数组,双指针+从后往前,JavaScript,详细注释

原题链接:https://leetcode-cn.com/problems/merge-sorted-array/



解题思路:



可参考官方题解的“方法三 : 双指针 / 从后往前”。



  1. 如果从nums1的最后一位按从大到小顺序往前存,最后一定会得到正确排序的数组,且不会有重复。

  2. 使用双指针从后往前遍历,遍历完任意一个数组的有效值后退出。

  3. 由于nums1已经排序,遍历完成之后,只需要判断nums2是否完成遍历即可。



/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function (nums1, m, nums2, n) {
let index1 = m - 1; // 用于遍历nums1。
let index2 = n - 1; // 用于遍历nums2。
let index = m + n - 1; // 表示实际存储数据的位置
// 使用双指针遍历,遍历完任意一个数组的有效值后退出。
while (index1 >= 0 && index2 >= 0) {
nums1[index--] = nums1[index1] >= nums2[index2] ? nums1[index1--] : nums2[index2--];
}
/*
* 将nums2未完成遍历的元素一次性存入nums1,需要注意以下几点:
* 1. 当nums1完成遍历时,index1是-1,因为退出循环时还进行了一次Index--。
* 2. 此时index为下一次循环要存入数据的位置。
* 3. 如果nums2已完成遍历,nums1剩下的值都已排序好,不需要操作。
*/
index1 === -1 && nums1.splice(0, index + 1, ...nums2.slice(0, index + 1));
};



发布于: 2020 年 08 月 17 日阅读数: 46
用户头像

Lee Chen

关注

还未添加个人签名 2018.08.29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:88. 合并两个有序数组,双指针+从后往前,JavaScript,详细注释