两个正序数组 找中位数_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)


相关推荐

  • Android开发:仿美团下拉列表菜单,帮助类,复用简单

    Android开发:仿美团下拉列表菜单,帮助类,复用简单

  • 静态路由介绍_静态路由下一跳地址类型

    静态路由介绍_静态路由下一跳地址类型网络上通过各种设备传递数据,最常见的就是路由器和交换机。本篇介绍路由器的静态路由协议。先简要说一下路由条目和路由表(熟悉的可略过):一个数据包从源IP地址到目标IP地址间可能穿过多个路由器,也可能有多条路径通往目标IP地址。那路由器收到数据后,如何知道哪个端口能通往目标地址呢?如果多个端口都可通往目标地址,选择用哪个端口才是最优路径呢?依据的就是路由表。路由表就是路由器的灵魂,是多个路由条目的…

  • allure 报告[通俗易懂]

    allure 报告[通俗易懂]一、简介二、下载安装三、报告生成四、环境配置五、Python使用allure方法一、简介官方文档:https://docs.qameta.io/allure/二、下载安装1、linux下载安装先检查是否安装npm:whichnpm 未安装npm的话:curl–silent–locationhttps://rpm.nodesource.com/setup_10.x|bash- 安装:yuminstall-ynodejs …

  • 截图bat文件_dos批处理

    截图bat文件_dos批处理******批处理bat命令快速截图********set”p=E:\Test\”::设置截图保存的路径,注意结尾要有\sett=%date:~0,4%%date:~5,2%%date:~8,2%_%time:~0,2%%time:~3,2%%time:~6,2%::设置当前的时间,用于截图的命名adbshell/system/bin/screencap-p/sdc…

  • android加密参数定位方法

    android加密参数定位方法作者正在编写一本爬虫逆向相关的书籍《书名还没有想好》。目前刚写了50页,上图是文章目录的一部分,想问一下大家现在对哪阶段的内容会更感兴趣,或者哪部分的内容会更有学习力,或者帮我想个书名。可在本文末留言告知,感谢大家。下面开始本文正文内容。在逆向一个Android程序时,如果只是盲目的分析需要阅读N多代码才能找到程序的关键点或Hook点,本文将分享一下如何快速的找到APP程序的加密参数位置,其实不论是找关键位置、找hook点,找加密参数、代码逻辑追踪,都是类似的处理方法。巧用搜索-静态分析

  • 最长上升子序列(LIS)算法

    最长上升子序列(LIS)算法LIS定义LIS(LongestIncreasingSubsequence)最长上升子序列 一个数的序列bi,当b1&lt;b2&lt;…&lt;bS的时候,我们称这个序列是上升的。对于给定的一个序列(a1,a2,…,aN),我们可以得到一些上升的子序列(ai1,ai2,…,aiK),这里1&lt;=i1&lt;i2&lt;…&lt;iK…

发表回复

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

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