88.合并两个有序数组

LeetCode LeetCode 数组 双指针 排序
发布时间 :
字数:2.4k 阅读 : 评论:
  1. 88.合并两个有序数组
    1. 88.1 题目
    2. 88.2 题解
      1. 方法一：双指针从后往前遍历
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：Array.Copy 和排序
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：合并后排序
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 88.3 代码
    4. 88.4 运行结果

88.合并两个有序数组

88.1 题目

给你两个按非递减顺序排列的整数数组 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 中。

88.2 题解

方法一：双指针从后往前遍历

思路

由于 nums1 末尾有足够空间，可以从后往前填充，避免覆盖未处理的元素。用三个指针：nums1Index 指向 nums1 有效元素末尾，nums2Index 指向 nums2 末尾，nowSetIndex 指向填充位置。每次比较两个数组当前元素，将较大的放入填充位置。如果 nums2 还有剩余元素，继续填入。

核心思想：从后往前填充，避免覆盖，双指针比较。

具体步骤：

  1. 初始化指针：i = m - 1, j = n - 1, k = m + n - 1。
  2. 当 i >= 0 && j >= 0：
    • 如果 nums1[i] >= nums2[j]：nums1[k] = nums1[i]，i--
    • 否则：nums1[k] = nums2[j]，j--
    • k--
  3. 如果 j >= 0，将 nums2 剩余元素填入。

举例：对于 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3：

  • i=2, j=2, k=5：nums1[2]=3 < nums2[2]=6，nums1[5]=6，j=1
  • i=2, j=1, k=4：nums1[2]=3 < nums2[1]=5，nums1[4]=5，j=0
  • i=2, j=0, k=3：nums1[2]=3 > nums2[0]=2，nums1[3]=3，i=1
  • i=1, j=0, k=2：nums1[1]=2 == nums2[0]=2，nums1[2]=2，j=-1
  • 结果：[1,2,2,3,5,6]

复杂度分析

  • 时间复杂度：O(m + n)，遍历两个数组。
  • 空间复杂度：O(1)，原地修改，无需额外空间。

代码

// 方法一：双指针从后往前遍历
// 从 nums1 和 nums2 的尾部开始，比较两者元素大小，将较大的元素放到 nums1 的尾部。
static void Merge1(int[] nums1, int m, int[] nums2, int n)
{
    // 如果 nums2 的长度为 0，则直接返回，无需合并
    if (n == 0) return;

    // 初始化 nums1、nums2 和合并后数组的索引
    int nums1Index = m - 1;  // nums1 数组的末尾索引
    int nums2Index = n - 1;  // nums2 数组的末尾索引
    int nowSetIndex = nums1.Length - 1;  // 合并后数组的末尾索引

    // 循环直到其中一个数组的所有元素都被合并完
    while (nums1Index >= 0 && nums2Index >= 0)
    {
        // 如果 nums2 中的当前元素大于或等于 nums1 中的当前元素
        if (nums2[nums2Index] >= nums1[nums1Index])
        {
            // 将 nums2 中的当前元素放入合并后数组中，并移动 nums2Index 指针
            nums1[nowSetIndex] = nums2[nums2Index];
            nums2Index--;
        }
        else
        {
            // 如果 nums2 中的当前元素小于 nums1 中的当前元素
            // 将 nums1 中尚未归位的较大元素放到尾部空位（与题解举例一致，不能用交换，否则会破坏已填好的尾部）
            nums1[nowSetIndex] = nums1[nums1Index];
            nums1Index--;
        }

        // 移动合并后数组的索引指针
        nowSetIndex--;
    }

    // 如果 nums2 中还有剩余元素，将其逐个放入合并后数组中
    while (nums2Index >= 0)
    {
        nums1[nowSetIndex] = nums2[nums2Index];
        nowSetIndex--;
        nums2Index--;
    }
}

方法二：Array.Copy 和排序

思路

先将 nums2 复制到 nums1 的末尾空位，然后对整个 nums1 数组进行排序。

简单直接，利用库函数，但时间复杂度较高。

举个例子：

  • nums1 = [1,2,3,0,0,0], m = 3
  • nums2 = [2,5,6], n = 3
  • 复制后：nums1 = [1,2,3,2,5,6]
  • 排序后：nums1 = [1,2,2,3,5,6]

复杂度分析

  • 时间复杂度：O((m + n) log(m + n))
  • 空间复杂度：O(log(m + n))

代码

// 方法二：Array.Copy 和排序
// 将 nums2 复制到 nums1 的末尾，然后对整个数组进行排序。
static void Merge2(int[] nums1, int m, int[] nums2, int n)
{
    Array.Copy(nums2, 0, nums1, m, n);
    Array.Sort(nums1);
}

方法三：合并后排序

思路

创建一个新数组，将 nums1 的有效部分和 nums2 复制进去，对新数组排序后，再复制回 nums1。

与方法二类似，但使用了额外的数组空间。

复杂度分析

  • 时间复杂度：O((m + n) log(m + n))
  • 空间复杂度：O(m + n)

代码

// 方法三：合并后排序
// 将 nums1 和 nums2 合并到一个新数组，然后对新数组进行排序，并将结果复制回 nums1。
static void Merge3(int[] nums1, int m, int[] nums2, int n)
{
    int[] mergedArray = new int[m + n];
    Array.Copy(nums1, 0, mergedArray, 0, m);
    Array.Copy(nums2, 0, mergedArray, m, n);
    Array.Sort(mergedArray);
    Array.Copy(mergedArray, nums1, m + n);
}

88.3 代码

using System;

public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

class Program
{
    static void Main()
    {
        #region 题目

        // 给你两个按 非递减顺序 排列的整数数组 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 中。

        #endregion

        #region 测试

        // 示例 1
        int[] nums1_1 = { 1, 2, 3, 0, 0, 0 };
        int m1 = 3;
        int[] nums2_1 = { 2, 5, 6 };
        int n1 = 3;
        Merge1(nums1_1, m1, nums2_1, n1);
        PrintArray("示例1", "方法1", nums1_1);

        // 示例 2
        int[] nums1_2 = { 1 };
        int m2 = 1;
        int[] nums2_2 = { };
        int n2 = 0;
        Merge2(nums1_2, m2, nums2_2, n2);
        PrintArray("示例2", "方法2", nums1_2);

        // 示例 3
        int[] nums1_3 = { 0 };
        int m3 = 0;
        int[] nums2_3 = { 1 };
        int n3 = 1;
        Merge1(nums1_3, m3, nums2_3, n3);
        PrintArray("示例3", "方法3", nums1_3);

        #endregion
    }

    #region 答案

    // 方法一：双指针从后往前遍历
    // 从 nums1 和 nums2 的尾部开始，比较两者元素大小，将较大的元素放到 nums1 的尾部。
    static void Merge1(int[] nums1, int m, int[] nums2, int n)
    {
        // 如果 nums2 的长度为 0，则直接返回，无需合并
        if (n == 0) return;

        // 初始化 nums1、nums2 和合并后数组的索引
        int nums1Index = m - 1;  // nums1 数组的末尾索引
        int nums2Index = n - 1;  // nums2 数组的末尾索引
        int nowSetIndex = nums1.Length - 1;  // 合并后数组的末尾索引

        // 循环直到其中一个数组的所有元素都被合并完
        while (nums1Index >= 0 && nums2Index >= 0)
        {
            // 如果 nums2 中的当前元素大于或等于 nums1 中的当前元素
            if (nums2[nums2Index] >= nums1[nums1Index])
            {
                // 将 nums2 中的当前元素放入合并后数组中，并移动 nums2Index 指针
                nums1[nowSetIndex] = nums2[nums2Index];
                nums2Index--;
            }
            else
            {
                // 如果 nums2 中的当前元素小于 nums1 中的当前元素
                // 将 nums1 中尚未归位的较大元素放到尾部空位（与题解举例一致，不能用交换，否则会破坏已填好的尾部）
                nums1[nowSetIndex] = nums1[nums1Index];
                nums1Index--;
            }

            // 移动合并后数组的索引指针
            nowSetIndex--;
        }

        // 如果 nums2 中还有剩余元素，将其逐个放入合并后数组中
        while (nums2Index >= 0)
        {
            nums1[nowSetIndex] = nums2[nums2Index];
            nowSetIndex--;
            nums2Index--;
        }
    }



    // 方法二：Array.Copy 和排序
    // 将 nums2 复制到 nums1 的末尾，然后对整个数组进行排序。
    static void Merge2(int[] nums1, int m, int[] nums2, int n)
    {
        Array.Copy(nums2, 0, nums1, m, n);
        Array.Sort(nums1);
    }

    // 方法三：合并后排序
    // 将 nums1 和 nums2 合并到一个新数组，然后对新数组进行排序，并将结果复制回 nums1。
    static void Merge3(int[] nums1, int m, int[] nums2, int n)
    {
        int[] mergedArray = new int[m + n];
        Array.Copy(nums1, 0, mergedArray, 0, m);
        Array.Copy(nums2, 0, mergedArray, m, n);
        Array.Sort(mergedArray);
        Array.Copy(mergedArray, nums1, m + n);
    }


    #endregion

    #region 辅助方法

    static void PrintArray(string example, string method, int[] array)
    {
        Console.Write($"{example} {method} 输出：[");
        for (int i = 0; i < array.Length; i++)
        {
            Console.Write(array[i]);
            if (i < array.Length - 1)
                Console.Write(", ");
        }

        Console.Write("]\n\n");
    }

    #endregion
}

88.4 运行结果

示例1 方法1 输出：[1, 2, 2, 3, 5, 6]

示例2 方法2 输出：[1]

示例3 方法3 输出：[1]
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏