合并两个有序数组

问题描述

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

**注意：**最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应忽略。nums2 的长度为 n。

示例

示例 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]，其中斜体加粗的元素来自 nums1。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 []。
合并结果是 [1]。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并 [] 和 [1]。
合并结果是 [1]。
注意，因为 m = 0，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

核心难点分析

1. 原地合并挑战

• 空间限制：必须在 nums1 数组内完成合并，不能使用额外的数组空间
• 数据覆盖风险：从前往后合并可能会覆盖 nums1 中尚未处理的元素
• 索引管理：需要正确管理多个指针的位置

2. 边界情况处理

• 空数组处理：其中一个数组为空的情况
• 大小差异：两个数组长度差异很大的情况
• 重复元素：两个数组中存在相同元素的处理

3. 算法选择

• 时间复杂度要求：需要在 O(m+n) 时间内完成
• 空间复杂度要求：原地操作，空间复杂度 O(1)

解法分析

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

核心思想：

• 从两个数组的末尾开始比较
• 将较大的元素放到 nums1 的末尾
• 避免了数据覆盖问题

算法步骤：

1. 设置三个指针：i 指向 nums1 有效元素末尾，j 指向 nums2 末尾，k 指向 nums1 总长度末尾
2. 比较 nums1[i] 和 nums2[j]，将较大者放入 nums1[k]
3. 移动相应指针，重复直到所有元素处理完毕

解法二：双指针从前往后 + 额外空间

核心思想：

• 使用额外数组存储合并结果
• 从前往后依次比较两个数组元素
• 最后将结果复制回 nums1

解法三：直接合并后排序

核心思想：

• 将 nums2 的所有元素复制到 nums1 的后半部分
• 对整个 nums1 进行排序

详细实现

Java 实现

解法一：双指针从后往前

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 三个指针：i指向nums1有效元素末尾，j指向nums2末尾，k指向nums1总长度末尾
        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--;
        }
        
        // 如果nums2还有剩余元素，复制到nums1
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
        
        // 注意：如果nums1还有剩余元素，它们已经在正确位置，无需移动
    }
}

解法二：额外空间法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 创建临时数组存储nums1的有效元素
        int[] temp = new int[m];
        System.arraycopy(nums1, 0, temp, 0, m);
        
        int i = 0, j = 0, k = 0;
        
        // 合并两个数组
        while (i < m && j < n) {
            if (temp[i] <= nums2[j]) {
                nums1[k] = temp[i];
                i++;
            } else {
                nums1[k] = nums2[j];
                j++;
            }
            k++;
        }
        
        // 复制剩余元素
        while (i < m) {
            nums1[k] = temp[i];
            i++;
            k++;
        }
        
        while (j < n) {
            nums1[k] = nums2[j];
            j++;
            k++;
        }
    }
}

Python 实现

解法一：双指针从后往前

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # 三个指针：i指向nums1有效元素末尾，j指向nums2末尾，k指向nums1总长度末尾
        i, j, k = m - 1, n - 1, m + n - 1
        
        # 从后往前合并
        while i >= 0 and j >= 0:
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        
        # 如果nums2还有剩余元素，复制到nums1
        while j >= 0:
            nums1[k] = nums2[j]
            j -= 1
            k -= 1

解法二：Pythonic 写法

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 直接使用Python的切片和排序
        nums1[m:] = nums2
        nums1.sort()

复杂度分析

解法一：双指针从后往前

• 时间复杂度：O(m + n)
  • 每个元素最多被访问一次
  • 总共需要处理 m + n 个元素
• 空间复杂度：O(1)
  • 只使用了常数个额外变量
  • 原地修改，不需要额外空间

解法二：额外空间法

• 时间复杂度：O(m + n)
  • 需要遍历两个数组各一次
• 空间复杂度：O(m)
  • 需要额外数组存储 nums1 的有效元素

解法三：直接排序

• 时间复杂度：O((m + n) log(m + n))
  • 排序算法的时间复杂度
• 空间复杂度：O(1) 或 O(log(m + n))
  • 取决于排序算法的实现

边界情况处理

1. 空数组情况

# nums2为空
nums1 = [1, 2, 3], m = 3, nums2 = [], n = 0
# 结果：[1, 2, 3]，无需任何操作

# nums1为空（有效元素为0）
nums1 = [0], m = 0, nums2 = [1], n = 1
# 结果：[1]，直接复制nums2

2. 大小差异极大

# nums1远大于nums2
nums1 = [1, 2, 3, 4, 5, 0], m = 5, nums2 = [6], n = 1
# 需要正确处理指针移动

# nums2远大于nums1
nums1 = [1, 0, 0, 0], m = 1, nums2 = [2, 3, 4], n = 3
# 需要确保nums2的所有元素都被复制

3. 重复元素处理

nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
# 相同元素需要保持稳定性

相关变种问题

1. 合并K个有序数组

def mergeKArrays(arrays):
    """
    使用分治法或优先队列
    时间复杂度：O(N log k)，其中N是所有元素总数，k是数组个数
    """
    import heapq
    
    result = []
    heap = []
    
    # 将每个数组的第一个元素加入堆
    for i, arr in enumerate(arrays):
        if arr:
            heapq.heappush(heap, (arr[0], i, 0))
    
    while heap:
        val, arr_idx, elem_idx = heapq.heappop(heap)
        result.append(val)
        
        # 如果该数组还有下一个元素，加入堆
        if elem_idx + 1 < len(arrays[arr_idx]):
            next_val = arrays[arr_idx][elem_idx + 1]
            heapq.heappush(heap, (next_val, arr_idx, elem_idx + 1))
    
    return result

2. 合并两个有序链表

def mergeTwoLists(list1, list2):
    """
    类似思路，但使用链表指针
    """
    dummy = ListNode(0)
    current = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # 连接剩余部分
    current.next = list1 or list2
    
    return dummy.next

3. 区间合并

def merge(intervals):
    """
    合并重叠区间
    """
    if not intervals:
        return []
    
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for current in intervals[1:]:
        if current[0] <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], current[1])
        else:
            merged.append(current)
    
    return merged

性能优化技巧

1. 早期终止优化

def merge_optimized(nums1, m, nums2, n):
    # 如果nums2为空，直接返回
    if n == 0:
        return
    
    # 如果nums1为空，直接复制nums2
    if m == 0:
        nums1[:n] = nums2[:n]
        return
    
    # 如果nums2的最大值小于nums1的最小值
    if nums2[n-1] < nums1[0]:
        # 将nums1向后移动，nums2放在前面
        nums1[n:m+n] = nums1[:m]
        nums1[:n] = nums2
        return
    
    # 如果nums1的最大值小于nums2的最小值
    if nums1[m-1] < nums2[0]:
        # 直接将nums2追加到nums1后面
        nums1[m:m+n] = nums2
        return
    
    # 正常的双指针合并
    i, j, k = m - 1, n - 1, m + n - 1
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

2. 内存访问优化

// 减少数组访问次数
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    
    // 缓存当前比较的值，减少数组访问
    while (i >= 0 && j >= 0) {
        int val1 = nums1[i];
        int val2 = nums2[j];
        
        if (val1 > val2) {
            nums1[k--] = val1;
            i--;
        } else {
            nums1[k--] = val2;
            j--;
        }
    }
    
    // 批量复制剩余元素
    if (j >= 0) {
        System.arraycopy(nums2, 0, nums1, 0, j + 1);
    }
}

实际应用场景

1. 数据库查询结果合并

def merge_query_results(result1, result2, key_func):
    """
    合并两个已排序的数据库查询结果
    """
    merged = []
    i = j = 0
    
    while i < len(result1) and j < len(result2):
        if key_func(result1[i]) <= key_func(result2[j]):
            merged.append(result1[i])
            i += 1
        else:
            merged.append(result2[j])
            j += 1
    
    merged.extend(result1[i:])
    merged.extend(result2[j:])
    
    return merged

2. 日志文件合并

def merge_log_files(file1_lines, file2_lines):
    """
    按时间戳合并两个日志文件
    """
    def get_timestamp(line):
        # 假设日志格式："2023-01-01 12:00:00 [INFO] message"
        return line[:19]  # 提取时间戳部分
    
    merged_logs = []
    i = j = 0
    
    while i < len(file1_lines) and j < len(file2_lines):
        if get_timestamp(file1_lines[i]) <= get_timestamp(file2_lines[j]):
            merged_logs.append(file1_lines[i])
            i += 1
        else:
            merged_logs.append(file2_lines[j])
            j += 1
    
    merged_logs.extend(file1_lines[i:])
    merged_logs.extend(file2_lines[j:])
    
    return merged_logs

3. 实时数据流合并

class StreamMerger:
    def __init__(self):
        self.buffer1 = []
        self.buffer2 = []
        self.merged_stream = []
    
    def add_to_stream1(self, data):
        self.buffer1.append(data)
        self._try_merge()
    
    def add_to_stream2(self, data):
        self.buffer2.append(data)
        self._try_merge()
    
    def _try_merge(self):
        # 当两个缓冲区都有数据时进行合并
        while self.buffer1 and self.buffer2:
            if self.buffer1[0] <= self.buffer2[0]:
                self.merged_stream.append(self.buffer1.pop(0))
            else:
                self.merged_stream.append(self.buffer2.pop(0))

常见错误与调试

1. 指针越界错误

# 错误示例：没有检查边界
def merge_wrong(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    
    # 错误：没有检查 i 和 j 的边界
    while k >= 0:
        if nums1[i] > nums2[j]:  # 可能越界！
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

# 正确示例：添加边界检查
def merge_correct(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    
    while i >= 0 and j >= 0:  # 正确的边界检查
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # 处理剩余元素
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

2. 忘记处理剩余元素

# 错误示例：忘记处理nums2的剩余元素
def merge_incomplete(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # 错误：忘记处理nums2的剩余元素！

# 正确示例：完整处理
def merge_complete(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # 正确：处理nums2的剩余元素
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

3. 调试技巧

def merge_with_debug(nums1, m, nums2, n):
    print(f"Initial: nums1={nums1}, m={m}, nums2={nums2}, n={n}")
    
    i, j, k = m - 1, n - 1, m + n - 1
    step = 0
    
    while i >= 0 and j >= 0:
        print(f"Step {step}: i={i}, j={j}, k={k}")
        print(f"  Comparing nums1[{i}]={nums1[i]} vs nums2[{j}]={nums2[j]}")
        
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            print(f"  Choose nums1[{i}], set nums1[{k}]={nums1[i]}")
            i -= 1
        else:
            nums1[k] = nums2[j]
            print(f"  Choose nums2[{j}], set nums1[{k}]={nums2[j]}")
            j -= 1
        k -= 1
        step += 1
        print(f"  Current nums1: {nums1}")
    
    while j >= 0:
        nums1[k] = nums2[j]
        print(f"Remaining: set nums1[{k}]={nums2[j]}")
        j -= 1
        k -= 1
    
    print(f"Final result: {nums1}")

面试要点总结

1. 关键考察点

• 算法选择能力：能否选择最优的双指针从后往前方法
• 边界处理：是否考虑各种边界情况
• 代码实现：指针操作是否正确，逻辑是否清晰
• 复杂度分析：能否准确分析时间和空间复杂度

2. 面试回答要点

面试官："请实现合并两个有序数组的算法。"

回答思路：
1. 问题理解："这是一个原地合并问题，需要将nums2合并到nums1中"
2. 方法选择："我选择双指针从后往前的方法，避免数据覆盖"
3. 算法描述："使用三个指针，从两个数组的末尾开始比较..."
4. 复杂度分析："时间复杂度O(m+n)，空间复杂度O(1)"
5. 边界情况："需要考虑空数组、大小差异等情况"

3. 进阶问题准备

• 如果要求稳定排序怎么办？
• 如果数组非常大，内存有限怎么处理？
• 如何扩展到合并K个有序数组？
• 如果数据是流式的，如何实时合并？

4. 代码模板

# 标准模板
def merge(nums1, m, nums2, n):
    # 边界检查
    if n == 0:
        return
    if m == 0:
        nums1[:n] = nums2
        return
    
    # 双指针从后往前
    i, j, k = m - 1, n - 1, m + n - 1
    
    while i >= 0 and j >= 0:
        if nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1
    
    # 处理剩余元素
    while j >= 0:
        nums1[k] = nums2[j]
        j -= 1
        k -= 1

总结

合并两个有序数组是一个经典的双指针问题，核心在于：

1. 算法选择：双指针从后往前是最优解，避免数据覆盖
2. 实现细节：正确管理三个指针，处理边界情况
3. 复杂度优化：达到 O(m+n) 时间复杂度和 O(1) 空间复杂度
4. 实际应用：在数据库、日志处理、流式计算等场景广泛应用

掌握这个问题不仅有助于解决类似的合并问题，还能加深对双指针技巧和原地算法的理解。在面试中，这是一个很好的展示算法思维和编程能力的题目。

学习建议

1. 理解原理：深入理解为什么从后往前比从前往后更优
2. 练习实现：多次手写代码，确保指针操作无误
3. 测试边界：用各种边界情况测试代码的正确性
4. 扩展思考：思考如何应用到其他合并问题
5. 性能优化：考虑各种优化策略和实际应用场景

扩展学习

• 归并排序：理解合并操作在排序算法中的应用
• 外部排序：学习大数据量下的合并策略
• 多路归并：掌握合并多个有序序列的方法
• 流式处理：了解实时数据流的合并技术