两个正序数组 找中位数_leetcode合并两个有序数组

两个正序数组 找中位数_leetcode合并两个有序数组原题连接给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。示例 1:输入:nums1 = [1,3], nums2 = [2]输出:2.00000解释:合并数组 = [1,2,3] ,中位数 2示例 2:输入:nums1 = [1,2], nums2 = [3,4]输出:2.50000解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5示例 3:输入:nums1 = [0,

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

原题连接
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例 1:

输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
示例 3:

输入:nums1 = [0,0], nums2 = [0,0]
输出:0.00000
示例 4:

输入:nums1 = [], nums2 = [1]
输出:1.00000
示例 5:

输入:nums1 = [2], nums2 = []
输出:2.00000
 

提示:

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
 

进阶:你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗?
题解

题解连接
在这里插入图片描述

class Solution { 

public:
int find(vector<int>&nums1,int begin1,vector<int>&nums2,int begin2,int k){ 

if(nums1.size() - begin1 > nums2.size() - begin2)return find(nums2,begin2,nums1,begin1,k);
int n = nums1.size() - begin1,m = nums2.size() - begin2;
if(n <= 0)return nums2[begin2 + k - 1];
if(k == 1)return min(nums1[begin1],nums2[begin2]);
int a1 = min(k / 2,n);
int a2 = k - a1;
if(nums1[begin1 + a1 - 1] < nums2[begin2 + a2 - 1])return find(nums1,begin1 + a1,nums2,begin2,k - a1);
else if(nums1[begin1 + a1 - 1] > nums2[begin2 + a2 - 1])return find(nums1,begin1,nums2,begin2 + a2,k - a2);
else return nums1[begin1 + a1 - 1];
}
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 

int n = nums1.size(),m = nums2.size();
if((n + m) & 1)return (double)find(nums1,0,nums2,0,(n + m + 1) / 2);
else{ 

int a = find(nums1,0,nums2,0,(n + m) / 2);
int b = find(nums1,0,nums2,0,(n + m) / 2 + 1);
return (a + b) / 2.0;
}
}
};
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168864.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • for循环将字典添加到列表中出现覆盖前面数据的问题

    for循环将字典添加到列表中出现覆盖前面数据的问题

  • 2020年软件测试前景_转行学软件测试的下场

    2020年软件测试前景_转行学软件测试的下场作为一名软件测试工程师,汇智妹可以负责任地告诉你:自信点,把“吗”去掉!为什么?本篇文章将从以下三个维度来为你解读:1.关于软件测试软件测试属新兴职业,且随着目前国内软件产业规模越来越大,软件行业也早已突破传统的作坊式生产,从单打独斗的开发模式升级为工业化、流水线式的生产模式,从而导致专业的软件测试人才需求缺口巨大。作为工业化产品质量的“把门”者,软件测试工程师已成为软件开发企业必不可少的技术人才。目前国内软件测试和开发人员比例大约在1:4~1:5,而国外测试和开发人员比例为1:1,由此

  • h5播放rtsp流_h5页面嵌入微信公众号

    h5播放rtsp流_h5页面嵌入微信公众号项目需求最近遇到一个新需求,将rtsp视频流接入h5页面中,rtsp是无法直接在h5页面上显示的,所以得通过一些手段将视频转成可以在h5上显示的格式;博主尝试过用nginx+ffmpeg转流,也尝试过用bilibili开源的flv.js转流;但最终效果都不太好,延迟高,卡顿时间长;后面发现一个神器VLC客户端,实时播放,完全不卡顿。前期准备VLC下载链接根据上方链接下载VLC客户端,根据自己的操作系统下载安装,博主使用的是windows10系统实际开发1.确保rtsp视频流可用,海康威视IP

  • 小型酒店管理系统毕业论文_简易酒店管理系统

    小型酒店管理系统毕业论文_简易酒店管理系统一需求:编写程序模拟酒店管理系统:预订和退订以及查看所有房间1需要有一个酒店类2需要有一个房间类3需要有一个客户端类publicclassTest{}二分析:客户端:1先打印所有房间2等待用户输入,根据输入情况判断是预订还是退订3等待用户输入房间号4调用酒店的预订/退订方法把房间号传入完成预订/退订功能…

  • java简历的项目经验怎么写_适合大学生做的java项目

    java简历的项目经验怎么写_适合大学生做的java项目前言今年的金三银四已经过去一大半了,在这其中参与过不少面试,2021都说工作不好找,这也是对开发人员的要求变向的提高了。之前在Github上收获15K+star的Java核心神技(这参数,质量多高就不用我多说了吧)非常全面,包含基础知识、Java集合、JVM、多线程并发、spring原理、微服务、Netty与RPC、Kafka、日记、设计模式、Java算法、数据库、Zookeeper、分布式缓存、数据结构等等内容非常丰富,已经帮很多人拿下互联网一线公司的offer美团一面:1、Concurr

  • ensemble database_oracle数据库执行计划怎么看

    ensemble database_oracle数据库执行计划怎么看原文来源:x2yline在生信进化树上的评论,http://www.biotrainee.com/thread-626-1-1.htmlEnsemble( ensembl.org网站是常用

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号