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大的数据,类似于快排递归调整数据使得左边所有数据小于当前数据,右边大于等于当前数据这一步骤

详解

假设 nums1nums2数组中元素个数都是大于 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 即为所求

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

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

AC代码

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

c++版本二

go版本

繁夜

发表评论


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

刷新评论