leetcode - 0004 median-of-two-sorted-arrays

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

解法一

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

这道题考的应该是并归排序。实际应用中很少去写这种算法，就直接使用了 List 的 sort() 方法来排序。

重复提交时有这个速度。

解法二

搜了一下标准库 heapq 中有并归排序 merge() 函数

from heapq import merge 

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

最后速度差不多

解法三

上面的解法都用到了排序。实际工作中我可能会这样写，简单方便好用。

但排序的复杂度是 O(nlogn) ，不符和题目 O(log(m+n)) 的要求

因为两个数组都已经是有序数组，所以排序不需要那么复杂的方法。直接两个数组从头开始取数，比大小，取小的那个，然后从被取的数组取下一个数，继续比较。这样的排序复杂度是多少？不懂怎么算复杂度，感觉应该是 O(m+n)。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = []
        i = j = 0
        while True:
            if i == len(nums1):
                nums.extend(nums2[j:])
                break
            if j == len(nums2):
                nums.extend(nums1[i:])
                break
            if nums1[i] < nums2[j]:
                nums.append(nums1[i])
                i += 1
            else:
                nums.append(nums2[j])
                j += 1

        print(nums)
        if len(nums) % 2 == 1:
            i = int(len(nums) / 2)
            return float(nums[i])
        else:
            i = int(len(nums) / 2)
            return (nums[i-1] + nums[i]) / 2

解法四

看了官方答案的分析，我的理解

两个数组A、B，长度分别为 m, n，（m 是较短的那个）。

对两个数组都切一刀，数组 A 切割点为 i，数组 B 的切割点为 j 。如果满足 A[i-1] < B[j] 且 B[j-1] < A[i] ，那么我们就刚好切到了中间。i 和 j 要满足切出来左、右两边的元素个数总和要相等（如果 m+n 为奇数的话，多出来的那一个放在左边）。

虽然很紧张，还是要下这一刀。半着眼睛我往数组 A 的靠中间位置 i 切了一刀，如果这个点就是要切的那个点，对应数组 B 上的位置是确定的：j = (m + n + 1) / 2 。如果我运气好的话，这一刀切了来得到 A[i-1] < B[j] 且 B[j-1] < A[i] ，那就是切中了。

此时如果把 A、B 左边的那部分合并排序得到 left，左边最大的数为 max_left A、B右边的部分排序合并得到 right，右边最小的数为 min_right 一定有 max_left < min_right

此时中位数怎么算呢：

如果 m+n 为奇数，那么中位数就是 max_left （因为多出来的一个放在了左边）如果 m+n 为偶数，那么中位数就是 (max_left + min_right) / 2

话说回来，我肯定没那么好运气一刀就切中。怎么切呢，二分法，在列表 A 上用二分法来切。

先切 A 的最中间，然后根据 j = (m+n+1)/2 就知道在列表 B 上切的位置。

切好后比较一下，比较是为了算出下一刀应该在 A 上往左半边切，还是往右半边切。

怎么比呢？

在列表 A 上的位置 i 切一刀：

如果 i 没超过列表A的最右边(i<m)，如果此时 A[i-1] > B[j]，下一刀往左切如果 i 没有切到列表A的最左边(i>0)，如果此时 B[j-1] > A[i]，下一刀往右切

如果上面两个条件都不满足，说明切中了。

写代码的时候，边界问题处理了好久，最后还是看了答案才搞对。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        m, n = len(A), len(B)
        if m > n:
            A, B = B, A
            m, n = n, m

        if n == 0:
            raise ValueError

        imin, imax = 0, m
        half_len = (m + n + 1) // 2

        while imin <= imax:
            i = (imin + imax) // 2
            j = half_len - i

            if i < m and B[j-1] > A[i]:
                imin = i + 1
            elif i > 0 and A[i-1] > B[j]:
                imax = i - 1
            else:
                if i == 0:
                    max_of_left = B[j-1]
                elif j == 0:
                    max_of_left = A[i-1]
                else:
                    max_of_left = max(A[i-1], B[j-1])

                if (m + n) % 2 == 1:
                    return float(max_of_left)

                if i == m:
                    min_of_right = B[j]
                elif j == n:
                    min_of_right = A[i]
                else:
                    min_of_right = min(A[i], B[j])

                return (max_of_left + min_of_right) / 2

meishaoming / blog

leetcode - 0004 median-of-two-sorted-arrays #68

解法一

解法二

解法三

解法四