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

题目

给定两个大小为 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

实现

第一种:利用二分策略

中位数:用来将一个集合划分为两个长度相等的子集,其中一个子集中的元素总是大于另一个子集中的元素。

由于题目要求时间复杂度为 O(log(m + n)),所以不能从两个有序数组的首尾挨个遍历来找到中位数(复杂度 O(m + n));而是要通过二分策略,通过每次比较,能够直接按比例的刷掉一组数字,最后找到中位数(复杂度 O(log(m + n)))。

nums1: [a1,a2,a3,...am]
nums2: [b1,b2,b3,...bn]

[nums1[:i],nums2[:j] | nums1[i:], nums2[j:]]

nums1 取 i 个数的左半边
nums2 取 j = (m+n+1)/2 - i 的左半边

只要保证左右两边 个数 相同,中位数就在 | 这个边界旁边产生,从而可以利用二分法找到合适的 i。

  • 状态:通过
  • 2085 / 2085 个通过测试用例
  • 执行用时: 160 ms, 在所有 C# 提交中击败了 99.18% 的用户
  • 内存消耗: 26.8 MB, 在所有 C# 提交中击败了 5.05% 的用户
public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.Length;
        int n = nums2.Length;
        if (m > n)
            return FindMedianSortedArrays(nums2, nums1);

        int k = (m + n + 1)/2;
        int left = 0;
        int right = m;
        while (left < right)
        {
            int i = (left + right)/2;
            int j = k - i;
            if (nums1[i] < nums2[j - 1])
                left = i + 1;
            else
                right = i;
        }
        int m1 = left;
        int m2 = k - left;
        int c1 = Math.Max(m1 == 0 ? int.MinValue : nums1[m1 - 1],
            m2 == 0 ? int.MinValue : nums2[m2 - 1]);

        if ((m + n)%2 == 1)
            return c1;

        int c2 = Math.Min(m1 == m ? int.MaxValue : nums1[m1],
            m2 == n ? int.MaxValue : nums2[m2]);
        return (c1 + c2)*0.5;        
    }
}

第二种:通过合并为一个有序数组的方式

思路:首先把两个有序数组合并为一个有序数组,然后根据数组长度来确定中位数,如果数组长度为偶数,那么返回两个中位数的平均值,如果数组长度为奇数,那么返回中位数。

python 实现

  • 执行结果:通过
  • 执行用时 :128 ms, 在所有 Python3 提交中击败了34.35%的用户
  • 内存消耗 :12.8 MB, 在所有 Python3 提交中击败了99.43%的用户
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        m = len(nums1)
        n = len(nums2)
        nums1.extend(nums2)# 合并
        nums1.sort()# 排序		
        if (m + n) & 1:# 如果是奇数 返回中位数
            return nums1[(m + n - 1) >> 1]
        else:# 返回两个中位数的平均值
            return (nums1[(m + n - 1) >> 1] + nums1[(m + n) >> 1]) / 2

C# 实现

  • 状态:通过
  • 2085 / 2085 个通过测试用例
  • 执行用时: 188 ms, 在所有 C# 提交中击败了 72.14% 的用户
  • 内存消耗: 26.9 MB, 在所有 C# 提交中击败了 5.05% 的用户
public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.Length;
        int len2 = nums2.Length;
        int len = len1 + len2;
        int[] nums = new int[len];
        Array.Copy(nums1, nums, len1);
        Array.Copy(nums2, 0, nums, len1, len2);
        Array.Sort(nums);
        if (len%2 == 0)
        {
            return (nums[len/2] + nums[len/2 - 1])*0.5;
        }
        return nums[len/2];        
    }
}

分享一下:

class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
    nums = nums1+nums2
    nums.sort()
    n = len(nums)
    if n%2 == 0:
        return (nums[int((n-1)/2)] + nums[int(n/2)])/2
    else:
        return (nums[n//2])