LeetCode: 4. Median of Two Sorted Arrays

引言

题目链接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

题目大意

给出两个升序的有序序列，找到两个序列合并后序列的中位数

Hint: You may assume nums1 and nums2 cannot be both empty.

官方希望复杂度为 O(log(m+n))

题解

对于一个长度为n的已排序数列 nums，

若n为奇数，中位数为 nums[n/2]

若n为偶数，则中位数 (nums[n/2-1] + nums[n/2]) / 2

方法一

一句话题解：走一次归并排序逻辑（先确定中位数下标过程中注意计算即可）

复杂度 O(m+n)，（明显和官方要求复杂度不是一个级别，目测后台数据比较水所以过了）

方法二

转换为寻找第k大的数据，类似于快排递归调整数据使得左边所有数据小于当前数据，右边大于等于当前数据这一步骤

详解

假设 nums1和 nums2数组中元素个数都是大于 k/2 的，且从 0 开始编号，比较 a = nums1[k/2-1] 和 b = nums2[k/2-1]

1. 如果 a < b 那么 nums1[0] 到 nums1[k/2-1] 这 k/2 个数在合并后的有序数组中，一定在第 k 小的数左边———— nums1数组中比 a 小的数一共是 k/2-1 个。 nums2数组中比 a 小的数最多有 k/2-1 个。因而合并后比 a 小的数最多有k/2-1+k/2-1 < k-2，即 a 最多是第 k-1 小的数。因此nums1数组前 k/2 个数可以剔除了
2. 如果 a > b 同理，剔除掉 nums2数组前 k/2 个数
3. 如果 a = b，a 即为所求

实际中若 nums1和 nums2数组中元素个数不足 k/2 个的话，只需要前两者分割数据个数等于k即可

复杂度：每次剔除掉 k 一半个元素，即时间复杂度是 O(logk)，对于此题, k=(m+n)/2 即复杂度 O(log(m+n))

AC代码

c++版本一（归并排序法，也是博主AC方法，为了不使用额外空间代码写得很挫，不够优雅）

c++版本二

go版本