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

题目分析

   寻找两个正序数组的中位数，这道题本身并不难，但是如何使用O(log(m + n))的时间复杂度求解是这道题目的难点。

合并数组

合并有序数组的方法是最容易想到的方法，在归并排序中就用到了这种思想，将两个有序的数组合并为一个，然后直接索引寻找中位数，时间复杂度为$O(m+n)$，空间复杂度为$O(m+n)$。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :nums1: List[int]
        :nums2: List[int]
        :rtype: float
        """
        nums = []
        len1, len2 = len(nums1), len(nums2)
        if len1 == 0:
            nums = nums2[:]
        elif len2 == 0:
            nums = nums1[:]
        else:
            p1 = p2 = 0
            while p1 < len1 and p2 < len2:
                if nums1[p1] < nums2[p2]:
                    nums.append(nums1[p1])
                    p1 += 1
                else:
                    nums.append(nums2[p2])
                    p2 += 1
            nums += nums2[p2:] if p1 == len1 else nums1[p1:]
        return nums[(len1 + len2) // 2] if (len1 + len2) % 2 else (nums[(len1 + len2) // 2 - 1] + nums[(len1 + len2) // 2]) / 2

双指针

因为不需要其他的数据，因此我们不需要引入一个新数组保存所有数据，只需要记录当前索引即。时间复杂度为$O(m+n)$，空间复杂度为$O(1)$。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :nums1: List[int]
        :nums2: List[int]
        :rtype: float
        """
        p1 = p2 = 0
        len1, len2 = len(nums1), len(nums2)
        prior, current = 0, 0
        for i in range((len1 + len2) // 2 + 1):
            prior = current
            if p1 < len1 and (p2 >= len2 or nums1[p1] < nums2[p2]):
                current = nums1[p1]
                p1 += 1
            else:
                current = nums2[p2]
                p2 += 1
        return current if (len1 + len2) % 2 else (current + prior) / 2

中位数算法

这道题还有更优的算法，利用中位数的性质和二分查找的思想，将两个数组分成左右两个部分，这种方法参考windliang在Leetcode题解中的思想。时间复杂度为$O(log(min(m+n)))$，空间复杂度为$O(1)$。

class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :nums1: List[int]
        :nums2: List[int]
        :rtype: float
        """
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        len1, len2 = len(nums1), len(nums2)
        min_index, max_index = 0, len1
        while 1:
            i = (min_index + max_index) // 2
            j = (len1 + len2 + 1) // 2 - i
            if i != len1 and nums2[j - 1] > nums1[i]:
                min_index = i + 1
            elif i != 0 and nums1[i - 1] > nums2[j]:
                max_index = i - 1
            else:
                if i == 0:
                    left_max = nums2[j - 1]
                elif j == 0:
                    left_max = nums1[i - 1]
                else:
                    left_max = max(nums1[i - 1], nums2[j - 1])
                if (len1 + len2) % 2 == 1:
                    return left_max
                if i == len1:
                    right_min = nums2[j]
                elif j == len2:
                    right_min = nums1[i]
                else:
                    right_min = min(nums1[i], nums2[j])
                return (left_max + right_min) / 2

刷题总结

  后面跟两种方法，我也是参考别人的题解，不仅思路清晰，而且代码简单，可以说膜拜了。这道题的难点在于二分法的应用，小伙伴们要多刷题，多见一见世面，比较不同算法之间的区别，增强自己的Coding能力。