LeetCode 面试题 10.01. 合并排序的数组

Categories:

题目描述
思路分析
1. 解法一：从后向前合并（推荐）
相似题目

题目描述

✅ 面试题 10.01. 合并排序的数组

思路分析

解法一：从后向前合并（推荐）

核心思路：

A 数组末尾预留空间，可从后往前填充。

使用三指针 i、j、k 分别指向 A 有效末尾、B 末尾、合并末尾。

每次选择较大元素放到 A[k]，避免覆盖未处理的 A。

复杂度分析：

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

空间复杂度：O(1)，原地合并。

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;

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

        while (j >= 0) {
            A[k] = B[j];
            j--;
            k--;
        }
    }
}

func merge(A []int, m int, B []int, n int) {
	i := m - 1
	j := n - 1
	k := m + n - 1

	for i >= 0 && j >= 0 {
		if A[i] > B[j] {
			A[k] = A[i]
			i--
		} else {
			A[k] = B[j]
			j--
		}
		k--
	}

	for j >= 0 {
		A[k] = B[j]
		j--
		k--
	}
}

相似题目

题目	难度	考察点
88. 合并两个有序数组	简单	双指针
21. 合并两个有序链表	简单	链表
977. 有序数组的平方	简单	双指针
986. 区间列表的交集	中等	双指针
23. 合并 K 个升序链表	困难	分治/堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/34153245