4.寻找两个正序数组的中位数

LeetCode LeetCode 热题100 数组 分治 二分查找
发布时间 :
字数:2.9k 阅读 : 评论:
  1. 4.寻找两个正序数组的中位数
    1. 4.1 题目
    2. 4.2 题解
      1. 方法一：合并重排序
        1. 思路
        2. 复杂度分析
        3. 代码
      2. 方法二：指针找中位数
        1. 思路
        2. 复杂度分析
        3. 代码
      3. 方法三：递归二分查找第k小数
    3. 4.3 代码
    4. 4.4 运行结果

4.寻找两个正序数组的中位数

4.1 题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n))。

示例：

  • 示例 1：

    • 输入：nums1 = [1,3], nums2 = [2]
    • 输出：2.00000
    • 解释：合并数组 = [1,2,3]，中位数 2

  • 示例 2：

    • 输入：nums1 = [1,2], nums2 = [3,4]
    • 输出：2.50000
    • 解释：合并数组 = [1,2,3,4]，中位数 (2 + 3) / 2 = 2.5

提示：

  • nums1.length == m
  • nums2.length == n
  • 0 <= m <= 1000
  • 0 <= n <= 1000
  • 1 <= m + n <= 2000
  • -10^6 <= nums1[i], nums2[i] <= 10^6

4.2 题解

方法一：合并重排序

思路

最直观的想法：把两个数组合并成一个，排序，然后找中位数。虽然时间复杂度不满足题目要求，但作为基准解法，有助于理解问题。

中位数的定义：

  • 如果数组长度是奇数，中位数就是中间那个数
  • 如果数组长度是偶数，中位数是中间两个数的平均值

举个例子：

  • [1,2,3] 长度3（奇数），中位数是 nums[1] = 2
  • [1,2,3,4] 长度4（偶数），中位数是 (nums[1] + nums[2]) / 2 = 2.5

复杂度分析

  • 时间复杂度：O((m+n)log(m+n))，合并后排序的时间
  • 空间复杂度：O(m+n)，存储合并后的数组

代码

// 方法一：合并重排序
// 将两个已排序的整数数组并成一个数组，然后对该列表进行排序。
// 最后，根据列表的长度和奇偶性确定中位数的计算方法。
static double FindMedianSortedArrays1(int[] nums1, int[] nums2)
{
    // 计算合并后数组的长度
    int mergeArrayLength = nums1.Length + nums2.Length;
    
    // 创建一个数组来存储合并后的数组
    int[] mergeArray = new int[nums1.Length + nums2.Length];
    
    // 将 nums1 和 nums2 数组的元素复制到合并后的数组中
    nums1.CopyTo(mergeArray, 0);
    nums2.CopyTo(mergeArray, nums1.Length);
    
    // 对合并后的数组进行排序
    Array.Sort(mergeArray);
    
    // 判断合并后的数组长度的奇偶性，以确定中位数的计算方法
    return mergeArrayLength % 2 == 0
        ? (mergeArray[mergeArrayLength / 2] + mergeArray[mergeArrayLength / 2 - 1]) / 2.0f
        : mergeArray[mergeArrayLength / 2];
}

方法二：指针找中位数

思路

既然两个数组已经有序了，我们其实不需要真正合并它们。用两个指针分别遍历两个数组，模拟合并后的遍历过程，只需要走到中位数的位置就够了。

关键点：

  • 我们只需要找到中位数，不需要完整的合并数组
  • 用 left 和 right 记录中间的两个值（处理偶数长度的情况）
  • 每次选择较小的元素移动指针

举个例子：nums1 = [1,2], nums2 = [3,4]

  • 合并后是 [1,2,3,4]，长度4，中位数位置是第2和第3个
  • 遍历过程：
    • i=0: left=-1, right=1（取nums1[0]）
    • i=1: left=1, right=2（取nums1[1]）
    • i=2: left=2, right=3（取nums2[0]）
  • 中位数 = (left + right) / 2 = (2 + 3) / 2 = 2.5

复杂度分析

  • 时间复杂度：O(m+n)，遍历到中位数位置
  • 空间复杂度：O(1)，只使用常数变量

代码

// 方法二：指针找中位数
// 不需要合并数组，两数组用两个指针指明当前索引，逐步移动指针
static double FindMedianSortedArrays2(int[] nums1, int[] nums2)
{
    // 获取两个数组的长度
    int nums1Length = nums1.Length;
    int nums2Length = nums2.Length;

    // 计算合并后的数组的总长度
    int allLength = nums1Length + nums2Length;

    // 用于存储中位数左右两侧的值
    int left = -1, right = -1;

    // 用于追踪两个数组的当前索引位置
    int nums1Index = 0, nums2Index = 0;

    // 遍历合并后的数组的一半长度（allLength / 2 + 1）
    for (int i = 0; i <= allLength / 2; i++)
    {
        // 将当前右侧的值赋给左侧
        left = right;

        // 如果数组 nums1 还有元素且 （数组 nums2 没有元素 或 数组 nums1 的元素 小于 数组 nums2 的元素)
        if (nums1Index < nums1Length && (nums2Index >= nums2Length || nums1[nums1Index] < nums2[nums2Index]))
        {
            // 将 numns1 中的元素赋给右侧，并更新 nums1Index
            right = nums1[nums1Index++];
        }
        else
        {
            // 数组 nums2 的元素更小或者数组 nums1 已经没有元素，将 nums2 中的元素赋给右侧，并更新 nums2Index
            right = nums2[nums2Index++];
        }
    }

    // 如果合并后的数组长度为偶数，返回中间两个元素的平均值；否则返回右侧的元素
    if ((allLength & 1) == 0)
        return (left + right) / 2.0;
    else
        return right;
}

方法三：递归二分查找第k小数

利用二分思想，每次排除 k/2 个元素。比较两个数组的第 k/2 个元素，较小的那个及其前面的元素一定不是第 k 小的，可以排除。递归在剩余部分查找第 k - 排除数量 小的元素。

复杂度分析：

  • 时间复杂度：O(log(m+n))，每次递归排除一半元素。
  • 空间复杂度：O(log(m+n))，递归调用栈的深度。
// 方法三：递归二分查找第k小数
// 二分查找，比较两数组的第k/2数，小的哪个说明前面的数不可能是第k小数了，减去小数值前面的元素，递归在新数组找第k小数
static double FindMedianSortedArrays3(int[] nums1, int[] nums2)
{
    // 获取输入数组的长度
    int nums1Length = nums1.Length;
    int nums2Length = nums2.Length;

    // 计算奇偶总长度的中点
    int left = (nums1Length + nums2Length + 1) / 2;
    int right = (nums1Length + nums2Length + 2) / 2;

    // 利用辅助函数计算中位数
    return (GetKthValueInTwoArrays(nums1, 0, nums1Length - 1, nums2, 0, nums2Length - 1, left) +
            GetKthValueInTwoArrays(nums1, 0, nums1Length - 1, nums2, 0, nums2Length - 1, right)) * 0.5;
}

// 查找两个已排序数组中第k个值的辅助函数
private static int GetKthValueInTwoArrays(int[] nums1, int nums1Start, int nums1End, int[] nums2, int nums2Start,
    int nums2End, int k)
{
    // 计算两个数组的剩余长度
    int nums1RemainingLength = nums1End - nums1Start + 1;
    int nums2RemainingLength = nums2End - nums2Start + 1;

    // 为确保 nums1 是较短的数组，如果 nums1 长度较长，则交换数组
    if (nums1RemainingLength > nums2RemainingLength)
        return GetKthValueInTwoArrays(nums2, nums2Start, nums2End, nums1, nums1Start, nums1End, k);

    // 基本情况：如果 nums1 为空，从 nums2 返回第 k 个元素
    if (nums1RemainingLength == 0)
        return nums2[nums2Start + k - 1];

    // 基本情况：如果 k 为 1，返回两个数组中第一个元素的最小值
    if (k == 1)
        return Math.Min(nums1[nums1Start], nums2[nums2Start]);

    // 计算将数组分为两半的索引
    int nums1Index = nums1Start + Math.Min(nums1RemainingLength, k / 2) - 1;
    int nums2Index = nums2Start + Math.Min(nums2RemainingLength, k / 2) - 1;

    // 比较两个数组的中点值
    if (nums1[nums1Index] > nums2[nums2Index])
    {
        // 在 nums2 的剩余部分递归搜索
        return GetKthValueInTwoArrays(nums1, nums1Start, nums1End, nums2, nums2Index + 1, nums2End,
            k - (nums2Index - nums2Start + 1));
    }
    else
    {
        // 在 nums1 的剩余部分递归搜索
        return GetKthValueInTwoArrays(nums1, nums1Index + 1, nums1End, nums2, nums2Start, nums2End,
            k - (nums1Index - nums1Start + 1));
    }
}

4.3 代码

using System;

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

        // 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
        // 请你找出并返回这两个正序数组的中位数。
        // 算法的时间复杂度应该为 O(log (m+n))。

        // 示例 1：
        // 输入：nums1 = [1,3], nums2 = [2]
        // 输出：2.00000
        // 解释：合并数组 = [1,2,3] ，中位数 2

        // 示例 2：
        // 输入：nums1 = [1,2], nums2 = [3,4]
        // 输出：2.50000
        // 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

        // 提示：
        // nums1.length == m
        // nums2.length == n
        // 0 <= m <= 1000
        // 0 <= n <= 1000
        // 1 <= m + n <= 2000
        // -106 <= nums1[i], nums2[i] <= 106

        #endregion

        #region 测试

        // 示例 1
        int[] nums1_1 = { 1, 3 };
        int[] nums2_1 = { 2 };
        double result11 = FindMedianSortedArrays1(nums1_1, nums2_1);
        Console.WriteLine($"示例1 方法1 输出：{result11}");
        double result12 = FindMedianSortedArrays3(nums1_1, nums2_1);
        Console.WriteLine($"示例1 方法2 输出：{result12}");
        double result13 = FindMedianSortedArrays3(nums1_1, nums2_1);
        Console.WriteLine($"示例1 方法3 输出：{result13}");

        // 示例 2
        int[] nums1_2 = { 1, 2 };
        int[] nums2_2 = { 3, 4 };
        double result21 = FindMedianSortedArrays1(nums1_2, nums2_2);
        Console.WriteLine($"示例1 方法1 输出：{result21}");
        double result22 = FindMedianSortedArrays2(nums1_2, nums2_2);
        Console.WriteLine($"示例1 方法2 输出：{result22}");
        double result23 = FindMedianSortedArrays3(nums1_2, nums2_2);
        Console.WriteLine($"示例1 方法3 输出：{result23}");

        #endregion
    }

    #region 答案

    // 方法一：合并重排序
    // 将两个已排序的整数数组并成一个数组，然后对该列表进行排序。
    // 最后，根据列表的长度和奇偶性确定中位数的计算方法。
    static double FindMedianSortedArrays1(int[] nums1, int[] nums2)
    {
        // 计算合并后数组的长度
        int mergeArrayLength = nums1.Length + nums2.Length;
        
        // 创建一个数组来存储合并后的数组
        int[] mergeArray = new int[nums1.Length + nums2.Length];
        
        // 将 nums1 和 nums2 数组的元素复制到合并后的数组中
        nums1.CopyTo(mergeArray, 0);
        nums2.CopyTo(mergeArray, nums1.Length);
        
        // 对合并后的数组进行排序
        Array.Sort(mergeArray);
        
        // 判断合并后的数组长度的奇偶性，以确定中位数的计算方法
        return mergeArrayLength % 2 == 0
            ? (mergeArray[mergeArrayLength / 2] + mergeArray[mergeArrayLength / 2 - 1]) / 2.0f
            : mergeArray[mergeArrayLength / 2];
    }


    // 方法二：指针找中位数
    // 不需要合并数组，两数组用两个指针指明当前索引，逐步移动指针
    static double FindMedianSortedArrays2(int[] nums1, int[] nums2)
    {
        // 获取两个数组的长度
        int nums1Length = nums1.Length;
        int nums2Length = nums2.Length;

        // 计算合并后的数组的总长度
        int allLength = nums1Length + nums2Length;

        // 用于存储中位数左右两侧的值
        int left = -1, right = -1;

        // 用于追踪两个数组的当前索引位置
        int nums1Index = 0, nums2Index = 0;

        // 遍历合并后的数组的一半长度（allLength / 2 + 1）
        for (int i = 0; i <= allLength / 2; i++)
        {
            // 将当前右侧的值赋给左侧
            left = right;

            // 如果数组 nums1 还有元素且 （数组 nums2 没有元素 或 数组 nums1 的元素 小于 数组 nums2 的元素)
            if (nums1Index < nums1Length && (nums2Index >= nums2Length || nums1[nums1Index] < nums2[nums2Index]))
            {
                // 将 numns1 中的元素赋给右侧，并更新 nums1Index
                right = nums1[nums1Index++];
            }
            else
            {
                // 数组 nums2 的元素更小或者数组 nums1 已经没有元素，将 nums2 中的元素赋给右侧，并更新 nums2Index
                right = nums2[nums2Index++];
            }
        }

        // 如果合并后的数组长度为偶数，返回中间两个元素的平均值；否则返回右侧的元素
        if ((allLength & 1) == 0)
            return (left + right) / 2.0;
        else
            return right;
    }

    // 方法三：递归二分查找第k小数
    // 二分查找，比较两数组的第k/2数，小的哪个说明前面的数不可能是第k小数了，减去小数值前面的元素，递归在新数组找第k小数
    static double FindMedianSortedArrays3(int[] nums1, int[] nums2)
    {
        // 获取输入数组的长度
        int nums1Length = nums1.Length;
        int nums2Length = nums2.Length;

        // 计算奇偶总长度的中点
        int left = (nums1Length + nums2Length + 1) / 2;
        int right = (nums1Length + nums2Length + 2) / 2;

        // 利用辅助函数计算中位数
        return (GetKthValueInTwoArrays(nums1, 0, nums1Length - 1, nums2, 0, nums2Length - 1, left) +
                GetKthValueInTwoArrays(nums1, 0, nums1Length - 1, nums2, 0, nums2Length - 1, right)) * 0.5;
    }

    // 查找两个已排序数组中第k个值的辅助函数
    private static int GetKthValueInTwoArrays(int[] nums1, int nums1Start, int nums1End, int[] nums2, int nums2Start,
        int nums2End, int k)
    {
        // 计算两个数组的剩余长度
        int nums1RemainingLength = nums1End - nums1Start + 1;
        int nums2RemainingLength = nums2End - nums2Start + 1;

        // 为确保 nums1 是较短的数组，如果 nums1 长度较长，则交换数组
        if (nums1RemainingLength > nums2RemainingLength)
            return GetKthValueInTwoArrays(nums2, nums2Start, nums2End, nums1, nums1Start, nums1End, k);

        // 基本情况：如果 nums1 为空，从 nums2 返回第 k 个元素
        if (nums1RemainingLength == 0)
            return nums2[nums2Start + k - 1];

        // 基本情况：如果 k 为 1，返回两个数组中第一个元素的最小值
        if (k == 1)
            return Math.Min(nums1[nums1Start], nums2[nums2Start]);

        // 计算将数组分为两半的索引
        int nums1Index = nums1Start + Math.Min(nums1RemainingLength, k / 2) - 1;
        int nums2Index = nums2Start + Math.Min(nums2RemainingLength, k / 2) - 1;

        // 比较两个数组的中点值
        if (nums1[nums1Index] > nums2[nums2Index])
        {
            // 在 nums2 的剩余部分递归搜索
            return GetKthValueInTwoArrays(nums1, nums1Start, nums1End, nums2, nums2Index + 1, nums2End,
                k - (nums2Index - nums2Start + 1));
        }
        else
        {
            // 在 nums1 的剩余部分递归搜索
            return GetKthValueInTwoArrays(nums1, nums1Index + 1, nums1End, nums2, nums2Start, nums2End,
                k - (nums1Index - nums1Start + 1));
        }
    }

    #endregion
}

4.4 运行结果

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

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏