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

LeetCode LeetCode 数组 分治 二分查找
发布时间 :
字数:2.4k 阅读 : 评论:
  1. 4.寻找两个正序数组的中位数
    1. 4.1 题目
    2. 4.2 题解
      1. 合并重排序
      2. 指针找中位数
      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 题解

合并重排序

// 方法一：合并重排序
// 将两个已排序的整数数组并成一个数组，然后对该列表进行排序。
// 最后，根据列表的长度和奇偶性确定中位数的计算方法。
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小数
// 二分查找，比较两数组的第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-2024 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏