一个算法题

水木社区手机版

主题:一个算法题
楼主|iwannabe|2021-09-17 00:51:17|只看此ID
A,B是两个升序数组，长度为a，b

用O(log(a+b)) 的时间找到 AUB的中位数
--
FROM 120.229.207.*
1楼|galaxy123|2021-09-17 06:01:06|只看此ID
https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2481/Share-my-O(log(min(mn)))-solution-with-explanation

时间复杂度： O(log(min(m,n)))

【在 iwannabe 的大作中提到: 】
: A,B是两个升序数组，长度为a，b
:
: 用O(log(a+b)) 的时间找到 AUB的中位数

- 来自「最水木 for iPhone 11 Pro Max」
※ 修改:·galaxy123 于 Sep 17 06:22:54 2021 修改本文·[FROM: 74.88.40.*]
※ 来源:·最水木客户端·[FROM: 74.88.40.*]

修改:galaxy123 FROM 74.88.40.*
FROM 74.88.40.*
2楼|yellowChange|2021-09-17 12:21:58|只看此ID
这个太简单了吧
【在 iwannabe 的大作中提到: 】
: A,B是两个升序数组，长度为a，b
:
: 用O(log(a+b)) 的时间找到 AUB的中位数
--
FROM 114.253.76.*
3楼|mrunmatched|2021-09-17 12:52:52|只看此ID
是哦，好简单，一个数组不停二分，然后每次拿中间的数去另一个数组再二分查找就行了
【在 iwannabe 的大作中提到: 】
: A,B是两个升序数组，长度为a，b
:
: 用O(log(a+b)) 的时间找到 AUB的中位数
: --
:

发自「今日水木 on HMA-AL00」
--
FROM 223.104.38.*
4楼|qlogic|2021-09-17 15:41:47|只看此ID
需要二分吗，直接去头+尾/2那个不就行了吗，有序数组
【在 mrunmatched (mrunmatched) 的大作中提到: 】
: 是哦，好简单，一个数组不停二分，然后每次拿中间的数去另一个数组再二分查找就行
: 了
: 发自「今日水木 on HMA-AL00」
--
FROM 119.139.198.*
5楼|mrunmatched|2021-09-17 19:06:52|只看此ID
我说的二分就是这个意思
【在 qlogic 的大作中提到: 】
:
: 需要二分吗，直接去头+尾/2那个不就行了吗，有序数组
: --
:

发自「今日水木 on HMA-AL00」
--
FROM 223.104.38.*
6楼|hjjscofield|2021-09-18 02:18:48|只看此ID
都好强，当年挂在这个题上。至今，不会做，得想一想
【在 iwannabe 的大作中提到: 】
: A,B是两个升序数组，长度为a，b
:
: 用O(log(a+b)) 的时间找到 AUB的中位数
: --
:

发自「今日水木 on iPhone 12 Pro」
--
FROM 101.93.6.*