LeetCode系列之 (JavaScript) => 88. 合并两个有序数组

题目描述:         

LeetCode系列之 (JavaScript) => 88. 合并两个有序数组

【Leetcode 题目链接】:88. 合并两个有序数组 - 力扣(LeetCode) (leetcode-cn.com)

解题思路分析:  

  1. 在nums1中找到nums2 插入的位置,然后在整体排序;
  2. 或采用合并排序的方式,逐个位置判断需要插入的元素(还要考虑循环方向,比如下面的第三种解法);
  3. 由于m,n的大小不确定,所以还需要考虑覆盖和其中一个数组没有遍历结束的情况;

不同解法:         

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
// 利用的是Array里面的自带方法 - 方便熟悉
var merge = function(nums1, m, nums2, n) {
    nums1.splice(m,n,...nums2); // 插入nums2
    nums1.sort((a,b) => a-b); // 整体排序
};
// 使用三个指针进行排序,时间复杂度是O(n^2)
var merge = function(nums1, m, nums2, n){
    if(nums2.length == 0){
        return;
    }
    var k = 0, i = 0, j = 0; // k 表示插入的位置,i遍历nums1,j遍历nums2
    var newNums1 = nums1.slice(0,m);
    for(k ; k < m+n; k++){
        // 如果 nums2 遍历结束,将 nums1 直接加入
        if(j == n){
            while(i < m){
                nums1[n+i] = newNums1[i];
                i++;
            }
            // console.log(nums1)
            return;
        }
        // 如果 nums1 遍历结束,将 nums2 直接加入
        if(i == m){
            while(j < n){
                nums1[m+j] = nums2[j];
                j++;
            }
            // console.log(nums1)
            return;
        }
        if(newNums1[i] <= nums2[j]){ 
            nums1[k] = newNums1[i++];
        }else{
            nums1[k] = nums2[j++];
            
        }
    }
}
// 【继续改进】 -> 将nums1中需要排序的m个元素插入到尾部 -> 不用考虑如果nums2提前遍历完的情况
// 循环结束条件:nums2循环遍历完,不用考虑nums1遍历完
var merge = function(nums1, m, nums2, n){
    //将nums1中需要排序的m个元素插入到尾部
    //循环方向从后往前,如果m>n,就会有“重叠”,从前往后循环,就会造成覆盖,移动就会造成问题
    for(var count = 1; count <= m ; count++){
        nums1[m+n-count] = nums1[m-count];
    }
    //遍历 nums2
    var i = n; // 用来遍历nums1 
    var j = 0; // 用来遍历nums2
    var k = 0; // 代表插入的位置

    while(j < n){
        //如果遍历nums1结束,直接将nums2 加到最后 (这一块【可加可不加】,提交都能通过)
        if(k == m+j){// 或条件设为 i == n+m
            while(j < n){
                nums1[k++] = nums2[j++];
            }
            return;
        }
        if(nums1[i] <= nums2[j]){
            nums1[k] =  nums1[i++];
        }else{
            nums1[k] = nums2[j++];
        }
        k++;
    }
}
// 【继续改进】:从nums1的末尾开始,比较两个数组最大的值
//  循环方向从后向前,同样可以防止覆盖
var merge = function(nums1, m, nums2, n){
    var i = m-1,j = n-1,k = m+n-1;
    while(i >= 0 && j >= 0){
        if(nums1[i] > nums2[j]){
            nums1[k--] = nums1[i--];
        }else{
            nums1[k--] = nums2[j--];
        }
    }
    while(j >= 0){
        nums1[k--] = nums2[j--];
    }
}

参考链接:          

上一篇:mysql – 本地IP与环回的数据库访问速度?


下一篇:LeetCode进阶之路(二)java常用的数据结构