LeetCode: 4. Median of Two Sorted Arrays

LeetCode - The World's Leading Online Programming Learning Platform

题目大意 

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

解题思路 

一、最容易想到的办法是把两个数组合并,然后取出中位数。但是合并有序数组的操作是 O(m+n) 的,不符合题意。看到题目给的 log 的时间复杂度,很容易联想到二分搜索。

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int size = nums1.length + nums2.length;int index1 = 0;int index2 = 0;int end = size/2;int begin = end;if (size % 2 == 0) {begin = begin-1;}int [] result = new int[end];int index = 0;while (index1 + index2 < size && index <= end) {if (index1 > nums1.length - 1) {result[index++] = nums2[index2++];continue;}if (index2 > nums2.length - 1) {result[index++] = nums1[index1++];continue;}if (nums1[index1] <= nums2[index2]) {result[index++] = nums1[index1++];continue;}result[index++] = nums2[index2++];}return (result[begin] + result[end])/2d;}
}

二、去中位进行两个数组移动

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/135968.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

爆破shadow文件密码脚本(完成版)

在之前的博客Python爆破shadow文件密码脚本&#xff08;简化版&#xff09;中我们做了简化版的爆破shadow文件密码的python脚本&#xff0c;接下来在之前代码的基础上改进&#xff1a; import crypt shadow_line"root:$y$j9T$uEgezfJhn7Ov5naU8bzZt.$9qIqkWYObaXajS5iLDA…

Java 时间范围

前端使用Element-ui 时间范围组件 后端注意在Vo里面时间设置String类型不要设置Date类型 XMl组件字段映射成功性

Linux知识点 -- 网络基础(二)-- 应用层

Linux知识点 – 网络基础&#xff08;二&#xff09;-- 应用层 文章目录 Linux知识点 -- 网络基础&#xff08;二&#xff09;-- 应用层一、使用协议来实现一个网络版的计算器1.自定义协议2.守护进程3.使用json来完成序列化 二、HTTP协议1.概念2.HTTP协议请求和响应的报文格式3…

2023/9/18 -- C++/QT

作业 完善登录框 点击登录按钮后&#xff0c;判断账号&#xff08;admin&#xff09;和密码&#xff08;123456&#xff09;是否一致&#xff0c;如果匹配失败&#xff0c;则弹出错误对话框&#xff0c;文本内容“账号密码不匹配&#xff0c;是否重新登录”&#xff0c;给定两…

WebGL 视图矩阵、模型视图矩阵

目录 立方体由三角形构成 视点和视线 视点、观察目标点和上方向 视点&#xff1a; 观察目标点&#xff1a; 上方向&#xff1a; 在WebGL中&#xff0c;观察者的默认状态应该是这样的&#xff1a; 视图矩阵程序&#xff08;LookAtTriangles.js&#xff09; 实际上&…

仅做笔记用:Stable Diffusion 通过 ControlNet 扩展图片 / 扩图

发觉之前的 Outpainting 脚本效果仍旧不是很理想。这里又找了一下有没有效果更好的途径来扩图。于是就找到了通过 ControlNet 的方式来实现效果更好的扩图。这里临时记录一下在 Stable Diffusion 怎么使用 ControlNet 来扩展图片。 下载 control_v11p_sd15_inpaint_fp16.safet…

多线程详解(上)

文章目录 一、线程的概念1&#xff09;线程是什么2&#xff09;为甚要有线程&#xff08;1&#xff09;“并发编程”成为“刚需”&#xff08;2&#xff09;在并发编程中, 线程比进程更轻量. 3&#xff09;线程和进程的区别 二、Thread的使用1&#xff09;线程的创建继承Thread…

自定义类型:结构体

自定义类型&#xff1a;结构体 一&#xff1a;引入二&#xff1a;结构体类型的声明1&#xff1a;正常声明2&#xff1a;特殊声明 三&#xff1a;结构体变量的创建和初始化1:结构体变量的创建2&#xff1a;结构体变量的初始化 三&#xff1a;结构体访问操作符四&#xff1a;结构…

【C语言】每日一题(半月斩)——day3

目录 一&#xff0c;选择题 1.已知函数的原型是&#xff1a; int fun(char b[10], int *a); 2、请问下列表达式哪些会被编译器禁止【多选】&#xff08; &#xff09; 3、以下程序的输出结果为&#xff08; &#xff09; 4、下面代码段的输出是&#xff08; &#xff09;…

大数据学习1.1-Centos8虚拟机安装

1.创建新的虚拟机 2.选择稍后安装OS 3.选择Linux的CentOS8 4.选择安装路径 5.分配20g存储空间 6.自定义硬件 7.分配2g内存 8.分配2核处理器 9.选择镜像位置 10.开启虚拟机安装 推荐密码设置为root

61、SpringBoot -----跨域资源的设置----局部设置和全局设置

★ 跨域资源共享的意义 ▲ 在前后端分离的开发架构中&#xff0c;前端应用和后端应用往往是彻底隔离的&#xff0c;二者不在同一个应用服务器内、甚至不再同一台物理节点上。 因此前端应用和后端应用就不在同一个域里。▲ 在这种架构下&#xff0c;前端应用可能采用前端框架&a…

序列化和反序列化:将数据变得更加通用化

序列化与反序列化简介 序列化和反序列化是计算机领域中常用的概念&#xff0c;用于将对象或数据结构转换为字节序列&#xff08;序列化&#xff09;和将字节序列转换回对象或数据结构&#xff08;反序列化&#xff09;。 序列化是指将对象或数据结构转换为字节序列的过程。通…

前端VUE---JS实现数据的模糊搜索

实现背景 因为后端实现人员列表返回&#xff0c;每次返回的数据量在100以内&#xff0c;要求前端自己进行模糊搜索 页面实现 因为是实时更新数据的&#xff0c;就不需要搜索和重置按钮了 代码 HTML <el-dialogtitle"团队人员详情":visible.sync"centerDi…

uni-app跳转到另一个app

第一步&#xff1a; 首先要知道 app的包名 获取方式如下 第二步&#xff1a; 在第一个 demo1 app 一个页面中需要一个按钮去跳转 方法如下 <template><view class"content"><button click"tz">跳转</button></view> </…

如何在微软Edge浏览器上一键观看高清视频?

编者按&#xff1a;视频是当下最流行的媒体形式之一。但由于视频压缩、网络不稳定等原因&#xff0c;我们常常可以看到互联网上的很多视频其画面质量并不理想&#xff0c;尤其是在浏览器端&#xff0c;这极大地影响了观看体验。不过&#xff0c;近期微软 Edge 浏览器推出了一项…

FPGA纯verilog实现8路视频拼接显示,提供工程源码和技术支持

目录 1、前言版本更新说明免责声明 2、我已有的FPGA视频拼接叠加融合方案3、设计思路框架视频源选择OV5640摄像头配置及采集静态彩条视频拼接算法图像缓存视频输出 4、vivado工程详解5、工程移植说明vivado版本不一致处理FPGA型号不一致处理其他注意事项 6、上板调试验证并演示…

Jmeter接口测试简易步骤

使用Jmeter接口测试 1、首先右键添加一个线程组&#xff0c;然后我们重命名接口测试 2、在线程组上添加一个Http默认请求&#xff0c;并配置服务器的IP地址端口等信息 3、在线程组中添加一个HTTP请求&#xff0c;这里我们重命名“增加信用卡账户信息接口” 4、配置接口请求信息…

使用延迟队列解决分布式事务问题——以订单未支付过期,解锁库存为例

目录 一、前言 二、库存 三、订单 一、前言 上一篇使用springcloud-seata解决分布式事务问题-2PC模式我们说到了使用springcloud-seata解决分布式的缺点——不适用于高并发场景 因此我们使用延迟队列来解决分布式事务问题&#xff0c;即使用柔性事务-可靠消息-最终一致性方…

Kotlin simple convert ArrayList CopyOnWriteArrayList MutableList

Kotlin simple convert ArrayList CopyOnWriteArrayList MutableList Kotlin读写分离CopyOnWriteArrayList_zhangphil的博客-CSDN博客Java并发多线程环境中&#xff0c;造成死锁的最简单的场景是&#xff1a;多线程中的一个线程T_A持有锁L1并且申请试图获得锁L2&#xff0c;而多…

Redis缓存实现及其常见问题解决方案

随着互联网技术的发展&#xff0c;数据处理的速度和效率成为了衡量一个系统性能的重要指标。在众多的数据处理技术中&#xff0c;缓存技术以其出色的性能优化效果&#xff0c;成为了不可或缺的一环。而在众多的缓存技术中&#xff0c;Redis 以其出色的性能和丰富的功能&#xf…