【leetcode】4. Median of Two Sorted Arrays寻找两个有序数组的中位数

Hard 题。两个数组本身已经有序，题目要求在线性对数级别以内求中位数；我当时的做法比较「学生思维」：先合并再排序，能出结果，但复杂度离题面要求差一截。

题意理解

给定两个升序数组 nums1、nums2，求它们合并后的中位数。总长度 m + n 为奇数时，中位数是中间那个数；为偶数时，是中间两个数的平均值。例如 nums1 = [1,3]、nums2 = [2]，合并为 [1,2,3]，中位数是 2.0。

暴力思路

既然两个数组各自有序，最省事就是把它们拼成一个大数组，排序后按下标取中位。实现简单，也便于先验证逻辑对不对。

我的初次实现

class Solution:

    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:

        newList = nums1 + nums2

        newList.sort()

        result = 0

        if(len(newList)%2 != 0) :

            result = newList[math.ceil(len(newList)/2-1)]

        else:

            index = int(len(newList)/2)

            result = (newList[index] + newList[index-1])/2

        return result

注意代码里用了 math.ceil，文件头需要 import math（LeetCode 模板里有时会自带，自己本地跑要记得加）。

中位数下标

• 奇数长度 n：中间下标是 (n - 1) // 2，上面 ceil(n/2 - 1) 等价。
• 偶数长度：取 index = n // 2 和 index - 1 两个元素的平均。

成果

本地和 OJ 上这版能通过样例，说明取中位数的逻辑没问题。

问题

但是我们仔细观察，可以发现这个的时间复杂度是不够的。

• 合并 O(m + n)，sort() 平均 O((m+n) log(m+n))，空间 O(m + n)。
• 题面要求 O(log(m+n)) 量级，关键是不能把两个有序序列「打平再排」——要利用有序性做二分，在较短数组上划分割线，使左右两侧元素个数平衡，且左侧最大值 ≤ 右侧最小值。那就是经典的二分找划分点做法，我这篇文章只记了第一版，后续再补优化。

若只想快速 AC、数据不大，合并排序够用；面试或冲 Hard 评级，还得上二分。

版权声明: 本文首发于 指尖魔法屋-【leetcode】4. Median of Two Sorted Arrays寻找两个有序数组的中位数（https://blog.thinkmoon.cn/post/726-notes-leetcode-median-of/） 转载或引用必须申明原指尖魔法屋来源及源地址！