算法通过村第九关-二分(中序遍历)黄金笔记|二叉搜索树

文章目录

  • 前言
  • 1. 有序数组转二叉搜索树
  • 2. 寻找连个正序数组的中位数
  • 总结


前言


提示:有时候,我感觉自己一辈子活在两个闹钟之间,早上的第一次闹钟,以及5分钟之后的第二次闹钟。 --奥利弗·萨克斯《意识的河流》

每个专题都有简单题,有难的题目。这里就介绍两道有挑战的题,一道是关于二叉搜索树的,一道是从两个数组中寻找中位数的。

1. 有序数组转二叉搜索树

参考题目介绍:108. 将有序数组转换为二叉搜索树 - 力扣(LeetCode)

在这里插入图片描述
在这里插入图片描述
理论上如果要构造二叉搜索树,可以以升序序列中的任意一个元素作为根节点,以该元素左边的升序序列构建左子树,以该元素的右边的升序序列构建右子树,这样得到的树就是一棵二叉搜索树。本体要求高度平衡,一次我们需要选择升序序列的中间元素作为根节点,其本质就是二分查找的过程。

话不多说,看代码😎:

	/*** 升序数组转二叉搜索树* @param nums* @return*/public static TreeNode sortedArrayToBST(int[] nums) {return dfs(nums,0,nums.length - 1);}private static TreeNode dfs(int[] nums, int left, int right) {if (left > right){return null;}// 处理节点 总是选择中间位置左边的数字作为根节点int mid = left + ((right - left) >> 1);TreeNode root = new TreeNode(nums[mid]);root.left = dfs(nums,left,mid - 1);root.right = dfs(nums,mid + 1,right);return root;}

除了通过数组构造,是否可以通过一个个插入的方式来实现呢?当然可以。那如果从中间删除一个元素呢?

推荐一下题目:⭐⭐⭐⭐⭐

701. 二叉搜索树中的插入操作 - 力扣(LeetCode)

450. 删除二叉搜索树中的节点 - 力扣(LeetCode)

2. 寻找连个正序数组的中位数

参考题目介绍:4. 寻找两个正序数组的中位数 - 力扣(LeetCode)

在这里插入图片描述
在这里插入图片描述
对于本题,最值观的思路有一下两种:

  • 使用并归的方式,合并两个有序数组,得到一个大的有序数组。大的有序数组中间的元素,即使中位数。这种方式的时间复杂度为O(m + n),空间复杂度为O(m + n)
  • 直接找到中位数。由于两个数组的长度已知,因此中位数对应的两个数组的下标之和也是已知的。维护两个指针,初始分别指向两个数组的下标0,0的位置,每次将指针指向较小的指针后移一位,如果指针已经达到数组末尾,只需要移动另一个数组指针,直到到达中位数的位置。这样的方式可以将空间复杂度降低至O(1),但是时间复杂度仍是O(m + n).

如何把时间复杂度降低至O(log(m+n))呢?如果对时间复杂度的要求是log,通常都要考虑二分,快排或者堆三个方面。而对于有序的序列,通常要优先考虑使用二分来解决。

如果要使用二分,核心问题是基于什么规则将数据砍掉一半。而本题是两个序列,所以我们的核心问题是如何从两个序列中分别砍半,图示k = (m + n) >> 1;

在这里插入图片描述
根据中位数的定义,当 m + n是奇数时,中间的两个序列数组的第(m + n) >> 1个元素,当 m + n是偶数时,中间是两个有序数组中的第(m + n) >> 1个元素和第((m + n) >> 1)+ 1的平均值。因此,这道题可以转换为寻找两个有序数组中的第k小的数,其中k为(m + n) >> 1或者((m + n) >> 1)+ 1

假设两个有序数组分别是LA和LB。要找到第k个元素我饿们可以比较LA[k / 2 - 1]和LB[k / 2 -1]。由于LA[k / 2 - 1]和LB[k / 2 -1]的前面分别是LA[k / 2 - 2]和LB[k / 2 -2],即k / 2 - 1个元素,对于LA[k / 2 - 1]和LB[k / 2 -1]中的最小值,最多只会有[k / 2 - 1] + [k / 2 -1] <= k - 2个元素比它小,那么它不就是我们要的第k小的数了。

因此我们可以总结一下:

  • 如果LA[k / 2 - 1] < LB[k / 2 -1],则比LA[k / 2 - 1]小的最多有LA的前面k / 2 - 1个数和LB前面k / 2 - 1个数;即比LA[k / 2 - 1]小的数最多只有k - 2个,因此LA[k / 2 - 1]不可能是第k个数,所以LA[0]到LA[k / 2 - 1]也不可能是第k个数,可以全部舍弃掉
  • 如果LA[k / 2 - 1] > LB[k / 2 -1],则可以推理排除LB[0]到LB[k / 2 - 1]也不可能是第k个数,可以全部舍弃掉
  • 如果LA[k / 2 - 1] > LB[k / 2 -1],则可以归入第一种情况处理。
    在这里插入图片描述
    可以看到,比较LA[k / 2 - 1] > LB[k / 2 -1]之后,可以排除k / 2个不可能是第k小的数,查找范围缩小了一半。同时我们将排除后的数组上继续进行二分查找的话,并且根据我们排除的个数,减少k的值,这是因为我们排除的数都不大于第k小的数。

注意一下边界处理:

  • 如果LA[k / 2 - 1] 或者LB[k / 2 -1]越界,那么我们可以以选取对应数组中的最后一个元素。这种情况下,我们必须根据排除数的个数减少k的值,而不是直接将k减去k / 2.
  • 如果k = 1 我们只需要返回两数组的首元素的最小值即可。

分析了这么多,怎么写这个代码呢?🤔

	/*** 两个有序数组找中间值* @param nums1* @param nums2* @return*/public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 = nums1.length,length2 = nums2.length;int totalLength = length1 + length2;if (totalLength % 2 == 1){int midIndex = totalLength >> 1;double median = getKthElement(nums1,nums2,midIndex + 1);return median;}else{int midIndex1 = (totalLength >> 1) - 1;int midIndex2 = (totalLength >> 1);double median = (getKthElement(nums1,nums2,midIndex1 + 1) + getKthElement(nums1,nums2,midIndex2 + 1)) / 2.0;return median;}}private double getKthElement(int[] nums1, int[] nums2, int k) {int length1 = nums1.length,length2 = nums2.length;int index1 = 0, index2 = 0;int kthElement = 0;while(true){// 边界问题if (index1 == length1){return nums2[index2 + k - 1];}if(index2 == length2){return nums1[index1 + k - 1];}if (k == 1){return Math.min(nums1[index1],nums2[index2]);}// 正常情况int half = k >> 1;int newIndex1 = Math.min(index1 + half,length1) - 1;int newIndex2 = Math.min(index2 + half,length2) - 1;int pivot1 = nums1[newIndex1],pivot2 = nums2[newIndex2];if(pivot1 <= pivot2){k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;}else{k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}

总结

提示:二分进阶;二分搜索;中序遍历;递归算法;分治思想

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

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

相关文章

上海亚商投顾:沪指震荡反弹 汽车产业链全天强势

上海亚商投顾前言&#xff1a;无惧大盘涨跌&#xff0c;解密龙虎榜资金&#xff0c;跟踪一线游资和机构资金动向&#xff0c;识别短期热点和强势个股。 一.市场情绪 大小指数昨日集体反弹&#xff0c;沪指3100点失而复得&#xff0c;创业板指一度涨超1.5%&#xff0c;随后涨幅…

echarts学习总结

一、新建一个简单的Echarts 首先新建一个vue2的项目&#xff0c;项目中安装Echarts cnpm install echarts --save1、title标题组件&#xff0c;包含主标题和副标题。 2、tooltip提示框组件 3、 legend图例组件 4、 series

springboot项目中定时任务注解@Scheduled未按cron表达式执行

springboot项目中定时任务注解Scheduled未按cron表达式执行 背景问题复现原因分析解决方法其他原因 背景 在将一个类注入到ioc后&#xff0c;其中定义了几个定时任务&#xff0c;分别是每隔十秒执行一次&#xff0c;但实际情况却是半小时才执行一次&#xff0c;故开始分析原因&…

爬虫怎么批量采集完成任务

目录 一、了解网络爬虫 二、Python与网络爬虫 三、批量采集任务的实现 1.确定采集网站及关键词 2.安装相关库 3.发送请求并获取响应 4.解析HTML文档 5.提取文章内容 6.保存文章内容 7.循环采集多篇文章 8.增加异常处理机制 9.优化代码性能 四、注意事项 总结 在当…

细胞机器人系统的概念

摘要 本文讨论了一种新型机器人系统的理论和工程的概念基础。该系统由协作完成任务的自主机器人单元组成。本文在描述了该系统与细胞自动机和神经网络的相关性和差异后&#xff0c;建立了该系统的基础属性及其对机器人单元结构的影响、它们操作的空间以及它们完成全局任务的算法…

virtualbox安装的linux虚拟机安装并启动Tomcat过程(结合idea操作)记录,并使用宿主机访问页面

virtualbox安装的linux虚拟机安装并启动Tomcat过程&#xff08;结合idea操作&#xff09;记录&#xff0c;并使用宿主机访问页面 参考教程地址linux版本Tomcat下载地址上传解压 启动TomcatVirtualBox虚拟机本地可访问宿主机尚未可以访问关闭防火墙宿主机可以访问 参考教程地址 …

vivado乘法器IP核进行无符号与有符号数相乘问题的验证

本文验证乘法器IP核Multiplier进行无符号(unsigned)与有符号数(signed)相乘的正确性&#xff0c;其中也遇到了一些问题&#xff0c;做此记录。 配套工程&#xff1a;https://download.csdn.net/download/weixin_48412658/88354179 文章目录 问题的讨论验证过程IP核配置例化乘…

ElementUI之登陆+注册

一.什么是ElementUI 二.ElementUI完成用户注册登录界面搭建 使用命令npm install element-ui -S&#xff0c;添加Element-UI模块 导依赖 建立登录和注册页面 ​编辑 配置样式 编写登录页面&#xff08;Login&#xff09; 编写注册页面&#xff08;reginter&#xff09; …

基于Android+OpenCV+CNN+Keras的智能手语数字实时翻译——深度学习算法应用(含Python、ipynb工程源码)+数据集(五)

目录 前言总体设计系统整体结构图系统流程图 运行环境模块实现1. 数据预处理2. 数据增强3. 模型构建4. 模型训练及保存5. 模型评估6. 模型测试 系统测试1. 训练准确率2. 测试效果3. 模型应用1&#xff09;程序下载运行2&#xff09;应用使用说明3&#xff09;测试结果 相关其它…

Spring源码相关

总分结构回答&#xff0c;突出关键接口、类、方法名 run -> AbstractApplicationContext.refresh&#xff08;&#xff09;程序的入口 在IOC中的操作都是基于DefaultListableBeanFactory bd对象保存在map集合中 refresh方法宝包括了整个Spring的执行流程和bean的完整生命…

企业做软文推广的三大错误有哪些?媒介盒子为您解答

软文营销已经成为企业宣传的主要方式&#xff0c;但有很多企业来找媒介盒子咨询&#xff0c;明明花了大量成本来做软文推广&#xff0c;为什么就是没效果呢&#xff1f;小编看了下&#xff0c;发现大部分企业做软文推广效果不明显&#xff0c;基本上犯了三大错误&#xff0c;接…

解决 react 项目启动端口冲突

报错信息&#xff1a; Emitted error event on Server instance at:at emitErrorNT (net.js:1358:8)at processTicksAndRejections (internal/process/task_queues.js:82:21) {code: EADDRINUSE,errno: -4091,syscall: listen,address: 0.0.0.0,port: 8070 }解决方法&#xff…

OpenLayers实战,OpenLayers调用手机陀螺仪方向实现指南针效果

专栏目录: OpenLayers实战进阶专栏目录 前言 本章讲解OpenLayers如何使用手机陀螺仪实现指南针,除了需要调用陀螺仪外,还需要获取手机的实时位置。 通过获取到的实时位置显示箭头图标位置,通过获取陀螺仪水平方向来调整箭头指向。 注意:必须在https请求(带ssl证书)下才…

信创之国产浪潮电脑+统信UOS操作系统体验1:硬件及软件常规功能支持情况介绍

一、引言 由于公司要求支持国产信创&#xff0c;最近办公的笔记本电脑换成了软硬件全国产&#xff0c;由于国产操作系统是在开源linux基础上演进的&#xff0c;在换之前&#xff0c;非常担心操作不方便&#xff0c;周边应用软件少&#xff0c;功能差&#xff0c;内心是比较抗拒…

常见的文件格式

一、C:\fakepath\新建文本文档.txt [object String] 实现方式&#xff1a; <input onchange"test(this.value)" type"file"></input><script>function test(e){console.log(e,Object.prototype.toString.call(e))}</script> 二、…

第77篇:美国APT入侵西北工业大学使用的5款远控后门揭秘

Part1 前言 大家好&#xff0c;我是ABC_123。在几个月前&#xff0c;我反复研读国家计算机病毒应急处理中心的多篇报告及360安全公司发布的各种关于该事件的报道&#xff0c;再结合国外对于美国APT研究报告&#xff0c;花了半个多月的时间复盘了美国APT入侵中国西北工业大学的…

红米note13 秒解锁BL 跳过168 秒解锁BL,红米Redmi Note 13 Pro+ 系列 无需等待168小时,刷入magisk教程 刷机包下载

最近入手了一台红米note13&#xff0c;发现需要等待168小时才能解锁BL&#xff0c;这让我感到非常困扰。不过&#xff0c;经过一番研究&#xff0c;我发现了一个秒解锁BL的方法&#xff0c;无需等待168小时&#xff0c;而且还可以刷入magisk&#xff0c;非常方便。 首先&#x…

[C++ 网络协议] I/O流分离所带来的半关闭问题

1.问题和解决方法 根据所学内容&#xff0c;I/O流分离现如今有如下2种方法&#xff1a; 1.调用进程fork函数&#xff0c;分离出子进程&#xff0c;主进程和子进程分别进行输入流的读和输出流的写。 2.用FILE指针按读模式和写模式将输入流和输出流进行区分。 第一种方法&#…

概率深度学习建模数据不确定性

https://zhuanlan.zhihu.com/p/568912284理解论文 What uncertainties do we need in Bayesian deep learning for computer vision? &#xff08;NeurIPS 2017) [1]中的数据不确定性建模&#xff0c;并给出公式推导。论文[1]指出不确定性uncertainty分为随机不确定性(aleator…

华为云云耀云服务器L实例评测|华为云上安装etcd

文章目录 华为云云耀云服务器L实例评测&#xff5c;华为云上安装etcd一、什么是etcd官方硬件建议 二、华为云主机准备三、etcd安装1. 安装预构建的二进制文件2. 从源代码构建 四、etcd服务注册与发现1. 配置etcd2. 使用systemctl 管理启动etcd服务3. 注册服务4. 发现服务 五、其…