88.合并两个有序数组.md

88. 合并两个有序数组

url

题目

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

初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 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 = [1], m = 1, nums2 = [], n = 0
输出：[1]

方法

两个数组合并，三个指针的思想

• nums1、nums2的末尾索引为idx1 = m - 1和idx2 = n - 1
• 同理，合并后的末尾索引为idx = m + n - 1
• 所以捏，两个数组分别从后往前遍历进行比较对应的val，四种情况
• 如果idx1 < 0，说明数组1没有元素了，直接将数组2赋值
• 如果idx2 < 0，说明数字2没有元素了，直接将数组1赋值
• 如果nums[idx1] < nums[idx2]，因为从后往前遍历，因此将nums[idx2]的val赋值
• 如果nums[idx1] >= nums[idx2]，将nums[idx1]的val赋值

code

js

let merge = (nums1, m, nums2, n) => {
    let idx1 = m - 1, idx2 = n - 1;
    let idx = m + n - 1;
    while (idx1 >= 0 || idx2 >= 0) {
        if (idx1 < 0)
            nums1[idx--] = nums2[idx2--];
        else if (idx2 < 0)
            nums1[idx--] = nums1[idx1--];
        else if (nums1[idx1] < nums2[idx2])
            nums1[idx--] = nums2[idx2--];
        else
            nums1[idx--] = nums1[idx1--];
    }
    console.log(nums1);
}
merge([1,2,3,0,0,0], 3, [2, 5, 6], 3)

go

func merge(nums1 []int, m int, nums2 []int, n int) {
	idx1, idx2 := m - 1, n - 1
	idx := m + n - 1
	for idx1 >= 0 || idx2 >= 0 {
		if idx1 < 0 {
			nums1[idx] = nums2[idx2]
			idx--
			idx2--
		} else if idx2 < 0 {
			nums1[idx] = nums1[idx1]
			idx--
			idx1--
		} else if nums1[idx1] < nums2[idx2] {
			nums1[idx] = nums2[idx2]
			idx--
			idx2--
		} else {
			nums1[idx] = nums1[idx1]
			idx--
			idx1--
		}
	}
	fmt.Println(nums1)
}

java

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx1 = m - 1, idx2 = n - 1;
        int idx = m + n - 1;
        while (idx1 >= 0 || idx2 >= 0){
            if (idx1 < 0)
                nums1[idx--] = nums2[idx2--];
            else if (idx2 < 0)
                nums1[idx--] = nums1[idx1--];
            else if (nums1[idx1] < nums2[idx2])
                nums1[idx--] = nums1[idx2--];
            else
                nums1[idx--] = nums2[idx1--];
        }
    }
}