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版本

繁夜

发表评论

粗体 斜体 删除线 下划线 链接 图片 私信 颜色 代码 引用

:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论