LeetCode 88. 合并两个有序数组

Categories:

Tags:

题目描述
思路分析
1. 解法一：从后往前双指针（推荐）
2. 解法二：额外数组合并
相似题目

题目描述

✅ 88. 合并两个有序数组

题目：

给定两个按非递减顺序排列的整数数组 nums1 和 nums2，以及整数 m 和 n 分别表示各自有效元素数目。将 nums2 合并到 nums1 中，使合并后的数组仍按非递减顺序排列。结果须存储在 nums1 中（长度为 m + n，前 m 个为有效元素，后 n 个为占位的 0）。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：合并 [1,2,3] 与 [2,5,6]，结果为 [1,2,2,3,5,6]。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9

进阶：

能否设计时间复杂度为 O(m + n) 的算法？

思路分析

解法一：从后往前双指针（推荐）

核心思路：

nums1 有足够空间，直接从数组尾部开始填充。

指针 i 指向 nums1 有效末尾，j 指向 nums2 末尾，k 指向最终末尾。

每次将较大的数放到 nums1[k]，并移动对应指针。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别表示两个数组长度。

空间复杂度：O(1)，仅使用常数额外空间。

// 从后向前合并
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }

        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }
}

// 从后向前合并
func merge(nums1 []int, m int, nums2 []int, n int) {
	i := m - 1
	j := n - 1
	k := m + n - 1

	for i >= 0 && j >= 0 {
		if nums1[i] > nums2[j] {
			nums1[k] = nums1[i]
			i--
		} else {
			nums1[k] = nums2[j]
			j--
		}
		k--
	}

	for j >= 0 {
		nums1[k] = nums2[j]
		j--
		k--
	}
}

解法二：额外数组合并

核心思路：

使用额外数组按顺序归并两个有序数组。

再将结果拷贝回 nums1。

复杂度分析：

时间复杂度：O(m + n)，其中 m、n 分别表示两个数组长度。

空间复杂度：O(m + n)，用于临时数组。

// 额外数组合并
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        int i = 0, j = 0, k = 0;

        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) {
                temp[k++] = nums1[i++];
            } else {
                temp[k++] = nums2[j++];
            }
        }

        while (i < m) {
            temp[k++] = nums1[i++];
        }
        while (j < n) {
            temp[k++] = nums2[j++];
        }

        for (int t = 0; t < m + n; t++) {
            nums1[t] = temp[t];
        }
    }
}

// 额外数组合并
func merge(nums1 []int, m int, nums2 []int, n int) {
	temp := make([]int, 0, m+n)
	i, j := 0, 0

	for i < m && j < n {
		if nums1[i] <= nums2[j] {
			temp = append(temp, nums1[i])
			i++
		} else {
			temp = append(temp, nums2[j])
			j++
		}
	}

	for i < m {
		temp = append(temp, nums1[i])
		i++
	}
	for j < n {
		temp = append(temp, nums2[j])
		j++
	}

	copy(nums1, temp)
}

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	双指针
977. 有序数组的平方	简单	双指针
986. 区间列表的交集	中等	双指针
2516. 每种字符至少取 K 个	中等	滑动窗口
23. 合并 K 个升序链表	困难	分治、堆
283. 移动零	简单	双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/16510261