LeetCode_4: Median of Two Sorted Arrays

# 引言

题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

# 题目大意

给出两个升序的有序序列, 找到两个序列合并后序列的中位数

Hint: You may assume nums1 and nums2 cannot be both empty.

官方希望复杂度为O(log(m+n))

# 题解

对于一个长度为n的已排序数列nums,

若n为奇数, 中位数为nums[n/2]

若n为偶数, 则中位数(nums[n/2-1] + nums[n/2]) / 2

# 方法一

# 一句话题解

走一次归并排序逻辑(先确定中位数下标过程中注意计算即可)

复杂度O(m+n), (明显和官方要求复杂度不是一个级别, 目测后台数据比较水所以过了)

# 方法二

转换为寻找第k大的数据, 类似于快排递归调整数据使得左边所有数据小于当前数据, 右边大于等于当前数据这一步骤

详解

假设nums1和nums2数组中元素个数都是大于 k/2 的, 且从 0 开始编号, 比较 a = nums1[k/2-1] 和 b = nums2[k/2-1]

1. 如果 a < b 那么 nums1[0] 到 nums1[k/2-1] 这 k/2 个数在合并后的有序数组中, 一定在第 k 小的数左边————nums1数组中比 a 小的数一共是 k/2-1 个。nums2数组中比 a 小的数最多有 k/2-1 个。因而合并后比 a 小的数最多有k/2-1+k/2-1 < k-2, 即 a 最多是第 k-1 小的数。因此nums1数组前 k/2 个数可以剔除了
2. 如果 a > b 同理, 剔除掉 nums2数组前 k/2 个数
3. 如果 a = b, a 即为所求

实际中若nums1和nums2数组中元素个数不足 k/2 个的话, 只需要前两者分割数据个数等于k即可

复杂度：每次剔除掉 k 一半个元素, 即时间复杂度是O(logk), 对于此题,k=(m+n)/2 即复杂度O(log(m+n))

# AC代码

c++版本一(归并排序法, 也是博主AC方法, 为了不使用额外空间代码写得很挫, 不够优雅)

class Solution
{
  public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int total = nums1.size() + nums2.size();
        if (0 == total)
        {
            return 0;
        }
        if (2 == total)
        {
            if (0 == nums1.size())
            {
                return (nums2[0] + nums2[1]) * 1.0 / 2;
            }
            if (0 == nums2.size())
            {
                return (nums1[0] + nums1[1]) * 1.0 / 2;
            }
            return (nums1[0] + nums2[0]) * 1.0 / 2;
        }
        double medianNumSum = 0;
        int medianNum1Index = ((total + 1) >> 1) - 1;
        int medianNum2Index = total >> 1;
        int i = 0;
        int j = 0;
        for (; i < nums1.size() && j < nums2.size();)
        {
            if (nums1[i] < nums2[j])
            {
                ++i;
            }
            else
            {
                ++j;
            }
            if (i + j == medianNum1Index && i < nums1.size() && j < nums2.size())
            {
                medianNumSum += (nums1[i] < nums2[j] ? nums1[i] : nums2[j]);
            }
            if (i + j == medianNum2Index && i < nums1.size() && j < nums2.size())
            {
                medianNumSum += (nums1[i] < nums2[j] ? nums1[i] : nums2[j]);
            }
        }
        if (i + j <= medianNum2Index && i < nums1.size())
        {
            for (; i < nums1.size(); ++i)
            {
                if (i + j == medianNum1Index)
                {
                    medianNumSum += nums1[i];
                }
                if (i + j == medianNum2Index)
                {
                    medianNumSum += nums1[i];
                }
            }
        }
        if (i + j <= medianNum2Index && j < nums2.size())
        {
            for (; j < nums2.size(); ++j)
            {
                if (i + j == medianNum1Index)
                {
                    medianNumSum += nums2[j];
                }
                if (i + j == medianNum2Index)
                {
                    medianNumSum += nums2[j];
                }
            }
        }
        return medianNumSum / 2;
    }
};

c++版本二

class Solution
{
  public:
    double findKthValue(vector<int> &nums1, vector<int> &nums2, int start1, int len1, int start2, int len2, int k)
    {
        if (len1 > len2)
        {
            return findKthValue(nums2, nums1, start2, len2, start1, len1, k);
        }
        if (0 == len1)
        {
            return nums2[start2 + k - 1];
        }
        if (1 == k)
        {
            return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2];
        }
        int p = k / 2 < len1 ? k / 2 : len1;
        int q = k - p;
        if (nums1[start1 + p - 1] > nums2[start2 + q - 1])
        {
            return findKthValue(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q);
        }
        else if (nums1[start1 + p - 1] < nums2[start2 + q - 1])
        {
            return findKthValue(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p);
        }
        else
        {
            return nums1[start1 + p - 1];
        }
    }
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int total = nums1.size() + nums2.size();
        if (total & 1)
        {
            return findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (total >> 1) + 1);
        }
        else
        {
            return (findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), total >> 1) +
                findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (total >> 1) + 1)) / 2;
        }
    }
};

go版本

func findKthValue(nums1, nums2 []int, start1, len1, start2, len2, k int) float64 {
	if len1 > len2 {
		return findKthValue(nums2, nums1, start2, len2, start1, len1, k)
	}
	if 0 == len1 {
		return float64(nums2[start2+k-1])
	}
	if 1 == k {
		return math.Min(float64(nums1[start1]), float64(nums2[start2]))
	}
	var p, q int
	if k/2 < len1 {
		p = k / 2
	} else {
		p = len1
	}
	q = k - p
	if nums1[start1+p-1] > nums2[start2+q-1] {
		return findKthValue(nums1, nums2, start1, len1, start2+q, len2-q, k-q)
	} else if nums1[start1+p-1] < nums2[start2+q-1] {
		return findKthValue(nums1, nums2, start1+p, len1-p, start2, len2, k-p)
	} else {
		return float64(nums1[start1+p-1])
	}
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	lens := len(nums1) + len(nums2)
	if 1 == lens&1 {
		return findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2+1)
	} else {
		return (findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2) +
			findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2+1)) / 2
	}
}