Leetcode4寻找两个正序数组的中位数

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

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

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

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

 

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

二分查找变体
思路为，计算中位数需要1or2个数，把大于这些数的数字全都删掉，再找最大的数来计算中位数
删除的过程为二分查找，假设删m个数字，那么至少有一个数组中的m/2个数字是可以删掉的
执行用时：16 ms
内存消耗：5.9 MB

void discard(int *nums1, int *nums1Size, int *nums2, int *nums2Size, int n);

double findMedianSortedArrays(int *nums1, int nums1Size, int *nums2, int nums2Size)
{
    int total = nums1Size + nums2Size;
    double result = 0;
    if (total % 2 == 0)
    {
        discard(nums1, &nums1Size, nums2, &nums2Size, total / 2 - 1);
        // select the biggest number after discard
        if (nums1Size == 0)
            result = nums2[--nums2Size];
        else if (nums2Size == 0)
            result = nums1[--nums1Size];
        else if (nums1[nums1Size - 1] > nums2[nums2Size - 1])
            result = nums1[--nums1Size];
        else
            result = nums2[--nums2Size];
        // select the second biggest number after discard
        if (nums1Size == 0)
            result += nums2[--nums2Size];
        else if (nums2Size == 0)
            result += nums1[--nums1Size];
        else if (nums1[nums1Size - 1] > nums2[nums2Size - 1])
            result += nums1[--nums1Size];
        else
            result += nums2[--nums2Size];
        result = result / 2;
    }
    else
    {
        discard(nums1, &nums1Size, nums2, &nums2Size, total / 2);
        // select the biggest number after discard
        if (nums1Size == 0)
            result = nums2[--nums2Size];
        else if (nums2Size == 0)
            result = nums1[--nums1Size];
        else if (nums1[nums1Size - 1] > nums2[nums2Size - 1])
            result = nums1[--nums1Size];
        else
            result = nums2[--nums2Size];
    }
    return result;
}

void discard(int *nums1, int *nums1Size, int *nums2, int *nums2Size, int n)
{
    // discard the biggest n numbers from nums1 and nums2
    int m;
    while (n != 0)
    {
        m = n / 2;
        if (*nums1Size == 0)
        {
            *nums2Size -= n;
            n = 0;
        }
        else if (*nums2Size == 0)
        {
            *nums1Size -= n;
            n = 0;
        }
        else if (n == 1)
        {
            if (nums1[*nums1Size - 1] > nums2[*nums2Size - 1])
                *nums1Size -= 1;
            else
                *nums2Size -= 1;
            n = 0;
        }
        else if (*nums1Size < m)
        {
            if (nums1[0] > nums2[*nums2Size - m])
            {
                n -= *nums1Size;
                *nums1Size = 0;
            }
            else
            {
                *nums2Size -= m;
                n -= m;
            }
        }
        else if (*nums2Size < m)
        {
            if (nums1[*nums1Size - m] > nums2[0])
            {
                *nums1Size -= m;
                n -= m;
            }
            else
            {
                n -= *nums2Size;
                *nums2Size = 0;
            }
        }
        else
        {
            if (nums1[*nums1Size - m] > nums2[*nums2Size - m])
                *nums1Size -= m;
            else
                *nums2Size -= m;
            n -= m;
        }
    }
}