欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode题解 4. Median of Two Sorted Arrays 【Array】

程序员文章站 2024-02-29 17:22:34
...

题目:

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5


题意分析:
给出两个已经排好序的数组,求出他们的中位数


题目思路:

最笨的办法就是合并两个数组……然后sort,然后找中位数。O(nlogn)
第二笨的办法就是一个数一个数地合并两个数组,合并到中间就停止,返回答案。O(m+n)(m,n为两数组长度)

还有一种是二分搜索,时间复杂度是O(log (m+n)).(注:我自己没想到如何在两个数组中二分搜索,这是我看完讨论区高票答案后写的):
联想到中位数的定义,我们把数组A分成两部分:

Leetcode题解 4. Median of Two Sorted Arrays 【Array】


假设数组A有m个元素,则有m+1种分法。设左边元素个数为i,右边元素个数为m-i

对B也分成两部分:

Leetcode题解 4. Median of Two Sorted Arrays 【Array】


假设数组B有n个元素,则有n+1种分法。设左边元素个数为j,右边元素个数为n-j

这样,我们就把两个数组各自分成两个部分:

Leetcode题解 4. Median of Two Sorted Arrays 【Array】


如果我们能保证左边长度等于右边长度,并且A[i-1] <= b[j], B[j-1] <= A[i],那么我们要找的中位数即是:
Leetcode题解 4. Median of Two Sorted Arrays 【Array】

此时,我们设 i 为数组A左边长度,那么数组B的左边长度即为(m+n+1)/2 - i.这样我们就能保证左边长度总和等于右边
问题成为了找到一个i,使得B[j-1] <= A[i] && A[i-1] <= B[j]
这里, j = (m + n + 1)/(2) - i

实现二分查找:
先设定 i 的边界值为[imin, imax]; imin = 0, imax = m;
让 i = (imin + imax)/2, j = (m + n + 1)/2 - i
情况1:
B[j-1] <= A[i] && A[i-1] <= B[j]
说明找到了符合条件的i,停止二分搜索
情况2:
B[j-1] > A[i]
说明A[i]太小,由于数组都是按从小到大排序,那么我们需要增大 i 。
让imin = i+1
情况3:
A[i-1] > B[j]
说明A[i-1]太大,由于数组是按从小到大排序,我们需要减小 i。
让imax = i-1


AC代码:

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        m, n = len(nums1), len(nums2)
        if m > n:
            return self.findMedianSortedArrays(nums2, nums1)
        imin, imax, half = 0, m, (m + n + 1) // 2
        
        while imin <= imax:
            i = (imin + imax) // 2
            j = half - i
            if i < m and nums2[j - 1] > nums1[i]:
                imin = i + 1
            elif i > 0 and nums1[i - 1] > nums2[j]:
                imax = i - 1
            else:
                if i == 0:
                    max_left = nums2[j - 1]
                elif j == 0:
                    max_left = nums1[i - 1]
                else:
                    max_left = max(nums1[i - 1], nums2[j - 1])
                
                if (m + n) % 2 == 1:
                    return max_left
                
                if i == m:
                    min_right = nums2[j]
                elif j == n:
                    min_right = nums1[i]
                else:
                    min_right = min(nums1[i], nums2[j])
                
                return (max_left + min_right) / 2