【LeetCode】4. 寻找两个有序数组的中位数

题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例

示例一

nums1 = [1, 3]

nums2 = [2]

则中位数是 2.0

示例二

nums1 = [1, 2]

nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解题

中位数：一组数组中间位置的数，数组长度为奇数 = n / 2，数组长度为偶数 ( (n/2) + (n/2 +1) ) / 2

时间复杂度要求：O(log(m + n))

解法一、合并排序后取中值

将两个数据合并排序
根据合并后长度是奇数或偶数取中值

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    var result = new int[nums1.Length + nums2.Length];

    int i = 0, l = 0, r = 0;
    while (l < nums1.Length || r < nums2.Length)
    {
        if (r >= nums2.Length || (l < nums1.Length && nums1[l] < nums2[r]))   //右边数据扫描完或左边数据没扫描完并且小于右边
        {
            result[i++] = nums1[l++];
        }
        else
        {
            result[i++] = nums2[r++];
        }
    }

    if (result.Length % 2 == 0)

    {
        return (result[result.Length / 2 - 1] + result[result.Length / 2]) / 2.0d;
    }
    return result[result.Length / 2];
}

View Code

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

能求解，但时间复杂度不符合条件

解法二、扫描查找

解法一需要长度为（m+n)的数组，这个数组只是为了最后取值所用，我们需要两个数据中位数，只需要扫描到n/2，后面的扫描是没有需要

用合并排序的方法扫描数据
扫描到n/2返回值

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    int len = nums1.Length + nums2.Length;
    int previous = 0, current = 0;
    int l = 0, r = 0;

    for (int i = 0; i <= len / 2; i++)
    {
        previous = current;

            if (r >= nums2.Length || (l < nums1.Length && nums1[l] < nums2[r])) //右边数据扫描完或左边数据没扫描完并且小于右边
        {
            current = nums1[l++];
        }
        else
        {
            current = nums2[r++];
        }
    }

    if ((len % 2) == 0) return (previous + current) / 2.0d; //长度为偶数

    return current;
}

View Code

减少了一半的查询，只需要额外的5个字段。时间复杂度：O((m+n)/2)，还是没达到题目要求

解法三、二分查找

要想达到log级别时间复杂度，只能从两个数组是有序的这个条件下手，有序数据的查找应该从二分查找下手。

m = num1.length , n = num2.length

k = (m + n) / 2;

本题转换为寻找两个数组第 k 小的数

1. 奇数情况

1.1 初始化两个变量指向两个数组中间 i = m / 2; j = n / 2;

1.2 A[i] <= B[j] 则A[i]前面的数字都可以丢弃，这时候变成求A[i] ~ A[n] 和 B[0] ~ B[n]两个数组第（k - i -1)小的数

1.3 A[i] > B[j] 则B[j]前面的数字都可以丢弃，这时候变成求A[0] ~ A[n] 和 B[j] ~ B[n]两个数组第（k - j - 1)小的数

1.4 以此类推

1.5 k == 0，当前两个数组第一个数小的那个就是中位数

1.6 注意边界问题，数组长度为空或1，跳出递归的条件

2. 偶数情况

((k - 1) + k) /2

public double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
    if (nums1.Length < nums2.Length) return FindMedianSortedArrays(nums2, nums1);

    if (nums1 == null || nums1.Length <= 0) return FindMedian(nums2);

    if (nums2 == null || nums2.Length <= 0) return FindMedian(nums1);

    /*
        m = num1.length , n = num2.length
        k = (m + n) / 2;
        本题转换为寻找两个数组第 k 小的数

        1. 奇数情况
            1.1 初始化两个变量指向两个数组中间 i = m / 2; j = n / 2;
            1.2 A[i] <= B[j] 则A[i]前面的数字都可以丢弃，这时候变成求A[i] ~ A[n] 和 B[0] ~ B[n]两个数组第（k - i -1)小的数
            1.3 A[i] > B[j] 则B[j]前面的数字都可以丢弃，这时候变成求A[0] ~ A[n] 和 B[j] ~ B[n]两个数组第（k - j - 1)小的数
            1.4 以此类推
            1.5 k == 0，当前两个数组第一个数小的那个就是中位数
            1.6 注意边界问题，数组长度为空或1，跳出递归的条件
        2. 偶数情况
            ((k - 1) + k) /2
    */
    var len = nums1.Length + nums2.Length;

    if (len % 2 == 1) return FindMedianSortedArrays(nums1, 0, nums1.Length, nums2, 0, nums2.Length, len / 2);

    return (FindMedianSortedArrays(nums1, 0, nums1.Length, nums2, 0, nums2.Length, len / 2 - 1) + FindMedianSortedArrays(nums1, 0, nums1.Length, nums2, 0, nums2.Length, len / 2)) / 2.0d;
}

public double FindMedianSortedArrays(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k)
{
    //保证长的数组在前
    if ((end1 - start1) < (end2 - start2)) return FindMedianSortedArrays(nums2, start2, end2, nums1, start1, end1, k);

    if (k == 0) return Math.Min(nums1[start1], nums2[start2]);

    if ((end1 - start1) <= 1) return Math.Max(nums1[start1], nums2[start2]); //第一个数组长度为1的情况

    if ((end2 - start2) <= 1)   //第二数组长度为1的情况
    {
        if (nums1[start1 + k] <= nums2[start2]) return nums1[start1 + k];

        return Math.Max(nums1[start1 + k - 1], nums2[start2]);
    }
    if (k == 1) //k == 1，即第二小的数字，比较两组数组前面2个元素即可得到结果
    {
        if (nums1[start1 + 1] <= nums2[start2]) return nums1[start1 + 1];

        if (nums1[start1] >= nums2[start2 + 1]) return nums2[start2 + 1];

        return Math.Max(nums1[start1], nums2[start2]);
    }

    var i = Math.Min((end1 - start1), k) / 2;
    var j = Math.Min((end2 - start2), k) / 2;

    if (nums1[start1 + i] < nums2[start2 + j]) return FindMedianSortedArrays(nums1, start1 + i, end1, nums2, start2, end2, k - i);

    return FindMedianSortedArrays(nums1, start1, end1, nums2, start2 + j, end2, k - j);
}

public double FindMedian(int[] nums)
{
    if (nums == null || nums.Length <= 0) throw new Exception("no result");

    if (nums.Length % 2 == 0) return (nums[nums.Length / 2 - 1] + nums[nums.Length / 2]) / 2.0d; ;

    return nums[nums.Length / 2];
}

View Code

LeetCode提交通过

【LeetCode】4. 寻找两个有序数组的中位数

示例

相关知识