首页 > 试题广场 >

两个有序数组的中位数

[编程题]两个有序数组的中位数
  • 热度指数：25709 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。
示例1

输入

[],[1]

输出

1.00000
算法知识视频讲解
开通博客
头像 予辰
发表于 2020-07-08 11:37:40
题目描述有两个大小分别为m和n的有序数组A和B。请找出这两个数组的中位数。你需要给出时间复杂度在O(log (m+n))以内的算法。思路分析两个大小分别为m和n的有序数组，我们要找出它们的中位数，而且要求时间复杂度是对数级别的，那么我们自然而然地就会想到二分查找算法，可是要怎么进行呢？寻找这两个数组 展开全文
去ta的博客 赞 (13) 回复(0) 收起
头像 华科不平凡
发表于 2020-08-15 19:20:41
时间复杂度为O(log(m+n))，直接想到二分法。 求两个排序数组的中位数，即求两个排序数组中： 第k个数（k=(m+n+1)/2，如果m+n为奇数） 第k个数与第k+1个数的平均值（k=(m+n)/2,k+1=1+(m+n)/2，如果m+n为偶数） 问题转化为求两个数组中的第k个数，分情况讨 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 CnpandaXu
发表于 2020-07-16 16:52:42
双指针解决 class Solution {public: double findMedianSortedArrays(int A[], int m, int B[], int n) { int p1 = 0, p2 = 0; int left = -1, righ 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

链表 排序
难度：
68条回答 28063浏览

热门推荐

通过挑战的用户

查看代码

相关试题

两个有序数组的中位数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号