Python 版 LeetCode 刷题笔记 #4 寻找两个有序数组的中位数

今天这题目很有趣，困难级别，但被我一脸懵逼、试着试着就给搞定了。当然，我是忽略了其中的关键要求，没有办法，带上这个要求我暂时还搞不定，先浑水摸鱼下吧。

题目

中文题目

第 4 题 寻找两个有序数组的中位数：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例:

nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

英文题目

Question 4 Median of Two Sorted Arrays: 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)). You may assume nums1 and nums2 cannot be both empty. Example:

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

思路

题目中有一句超出我能力范围：“并且要求算法的时间复杂度为 O(log(m + n))。”之前有看过时间复杂度的概念，但还是对这里的要求没什么头绪。只好选择忽略这个条件来单纯实现功能吧。没了这个要求，感觉就很简单了，把两个有序数字加起来组成新的列表并进行排序。如果长度是单数，取最中间的项；如果长度是偶数，那么取中间两项的平均值。

代码

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # 将两个列表相加
        temp = nums1 + nums2
        # 相加后的结果排序
        temp.sort()
        # 排序后的列表长度
        length = len(temp)
        # 如果为单数，取中间项返回
        if length%2:
            return temp[int((length-1)/2)]
        # 如果为偶数，取中间两项的平均值返回
        else:
            return (temp[int(length/2)-1]+temp[int(length/2)])/2

提交答案

这次提交答案后，看到测评结果简直要感动哭了：

中文区结果：

执行用时 :60 ms, 在所有 Python3 提交中击败了70.21%的用户 内存消耗 :13.5 MB, 在所有 Python3 提交中击败了5.31%的用户

英文版结果：

Runtime: 88 ms, faster than 92.54% of Python3 online submissions for Median of Two Sorted Arrays. Memory Usage: 14.1 MB, less than 5.71% of Python3 online submissions for Median of Two Sorted Arrays.

说实话，提交完，我双手离开键盘、在等待 4000+ms 的出现，但是这个神奇的测试结果，让我说不出话来。按理说，我代码中用到的 sort() 是对整个相加后的列表进行排序，时间复杂度应该是 O(m + n) 吧，提交的答案应该是 O(log(m + n)) 的，我这竟然还能超过这么高比例的答案？

一番翻阅评论，发现了也有人用了这种鸡贼的方法并附上了相关分析：“python 的 list.sort 使用的是 timesort 这个机制，本质上是归并和插排的结合体，时间复杂度为 nlogn,最差为 nlogn, 最优为 n, 在这里的编译器里应该算在同一数量级，所以能通过，严格说，较大的数组应该不在复杂度要求内”。

分析来源：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/pythonliang-ge-you-xu-shu-zu-de-zhong-wei-shu-by-j/

结论

其实今天算偷懒了，参考了一众评论、推荐答案后，正规的解题思路是二分法，但可能有点超出预期工作量，所以就先不做深入研究了。想想出题的人也应该很无语，一个困难难度的题目，被掐去了关键要求，就被鸡贼地搞定了。

今天偷个懒，明天继续～