首页 > 试题广场 >

在两个长度相等的排序数组中找到上中位数

[编程题]在两个长度相等的排序数组中找到上中位数
  • 热度指数：33384 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。
上中位数：假设递增序列长度为n，为第n/2个数

数据范围：，

要求：时间复杂度 ，空间复杂度
进阶：时间复杂度为，空间复杂度为

示例1

输入

[1,2,3,4],[3,4,5,6]

输出

3

说明

总共有8个数，上中位数是第4小的数，所以返回3。
示例2

输入

[0,1,2],[3,4,5]

输出

2

说明

总共有6个数，那么上中位数是第3小的数，所以返回2
示例3

输入

[1],[2]

输出

1

备注:

算法知识视频讲解
开通博客
头像 LaN666
发表于 2021-03-07 21:10:00
精华题解 题目：给定两个有序数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。上中位数：假设递增序列长度为n，若n为奇数，则上中位数为第n/2+1个数；否则为第n/2个数 方法一：双指针假设两个数组为一个数组，先算出上中位数的位置。我们使用双指针去遍历两个数组，并且用一个数记录走 展开全文
去ta的博客 赞 (8) 回复(5) 收起
头像 未来0116
发表于 2021-07-10 12:28:49
精华题解 一.题目描述NC36在两个长度相等的排序数组中找到上中位数题目链接：https://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404ftpId=196&&tqId=37141&rp=1&ru=/acti 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 子夜降晴空
发表于 2021-03-24 20:14:15
class Solution { public: int findMedianinTwoSortedAray(vector<int>& arr1, vector<int>& arr2) { if(arr1.size() == 1) re 展开全文
去ta的博客 赞 (16) 回复(0) 收起
头像 小洋芋热爱NLP
发表于 2021-03-17 22:56:42
- 1、题目描述： - 2、题目链接：https://www.nowcoder.com/practice/6fbe70f3a51d44fa9395cfc49694404f?tab=answerKey -3、 设计思想：详细操作流程看下图： -4、视频讲解链接B站视频讲解 -5、代码：c++版本: 展开全文
去ta的博客 赞 (13) 回复(2) 收起
头像 自由的走狗
发表于 2020-12-27 20:29:30
import java.util.*; public class Solution { /** * find median in two sorted array * @param arr1 int整型一维数组 the array1 * @param arr 展开全文
去ta的博客 赞 (11) 回复(1) 收起
头像 漫漫云天自翱翔
发表于 2021-07-30 21:39:16
题解一：双指针 题解思路： 使用两个指针分别指向两个数组，由于两个数组长度相等，所以如果看成一个大数组的话，这个数组的长度一定为偶数。每次移动两者较小值的指针。当i+j==len表明找到中位数。 图示： 复杂度分析：时间复杂度： ： 只要一个到达数组末尾，就 展开全文
去ta的博客 赞 (9) 回复(0) 收起
头像 诗云panther
发表于 2021-08-11 19:23:30
class Solution {public: /** * find median in two sorted array * @param arr1 int整型vector the array1 * @param arr2 int整型vector the array2 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 月关雨辰
发表于 2021-09-12 00:39:02
不明白 哈哈 但用手画一画 就是这个规律:题解二：二分题解思路：首先两个数组都为N且有序，那么两个数组中间值两边数的个数是相同（长度为奇数）的或者一边多一个（长度为偶数），所以要考虑长度的奇偶。用mid1表示arr1中值index，mid2表示arr2中值index 长度为奇数①arr1[mid1] 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 总之就是非常可爱
发表于 2022-02-23 15:50:18
class Solution { public:     /**      * find median in two sorted array      * @param arr1 int整型vector the arr 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 白羊兔
发表于 2021-10-12 15:23:20
import java.util.*; //思路 暴力求解 public class Solution { /** * find median in two sorted array * @param arr1 int整型一维数组 the array1 * @ 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 旧岛
发表于 2021-07-07 11:24:37
write code here class Solution: def findMedianinTwoSortedAray(self , arr1 , arr2 ): for i in arr2: arr1.append(i) arr1.sort() leng 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 勤奋的猫
发表于 2022-06-20 19:06:45
import java.util.*; public class Solution {     /**      * find median&nb 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

数组 二分 分治
难度：
89条回答 4554浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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