当前位置: 首页 > news >正文

Leetcode 搜索旋转排序数组

在这里插入图片描述
这段代码是用于解决LeetCode第33题“搜索旋转排序数组”的Java解法。以下是对该算法思想的中文解释:

算法思想

  1. 二分查找的基本思路

    • 由于数组是部分有序的(被旋转过),我们可以利用二分查找的思想,逐步缩小搜索范围。
    • 但是与普通的二分查找不同,这里的数组被旋转过,所以需要先判断当前数组的哪个部分是有序的,再决定如何更新搜索范围。
  2. 判断有序区间

    • 通过比较nums[left]nums[mid],我们可以确定左半部分或右半部分是否是有序的。
    • 如果nums[left] <= nums[mid],说明左半部分是有序的。
    • 如果nums[left] > nums[mid],说明右半部分是有序的。
  3. 确定目标值在哪个区间

    • 如果左半部分是有序的,且目标值targetnums[left]nums[mid]之间(即nums[left] <= target < nums[mid]),那么我们将搜索范围缩小到左半部分,即更新right = mid - 1
    • 如果目标值不在左半部分,那么我们将搜索范围缩小到右半部分,即更新left = mid + 1
    • 同理,如果右半部分是有序的,且目标值targetnums[mid]nums[right]之间(即nums[mid] < target <= nums[right]),则搜索范围缩小到右半部分。
    • 否则,目标值在左半部分,因此更新right = mid - 1
  4. 返回结果

    • 如果找到目标值,则返回它的索引。
    • 如果循环结束后仍未找到目标值,则返回-1

Java 代码的逐行解释

class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length - 1;while (left <= right) {int mid = left + (right - left) / 2;// 检查中间元素是否为目标值if (nums[mid] == target) {return mid;}// 判断左半部分是否有序if (nums[left] <= nums[mid]) {// 检查目标值是否在左半部分if (nums[left] <= target && target < nums[mid]) {right = mid - 1;} else {left = mid + 1;}}// 右半部分是有序的else {// 检查目标值是否在右半部分if (nums[mid] < target && target <= nums[right]) {left = mid + 1;} else {right = mid - 1;}}}// 未找到目标值,返回-1return -1;}
}

时间复杂度

由于每次循环都会将搜索区间缩小一半,所以时间复杂度为 (O(\log n)),符合题目要求的高效查找。

总结

这个算法巧妙地利用了数组的部分有序特性,结合二分查找,在旋转数组中高效地查找目标值。

为什么如果nums[left] > nums[mid],说明右半部分是有序的。

如果nums[left] > nums[mid],说明左半区间存在旋转断点,而旋转断点之后的子数组都是有序的,所以右半部分是有序的。

nums[left] > nums[mid]时,确实可以判断左半区间存在旋转断点,这意味着左半部分并不是完全有序的。而旋转断点之后的子数组会保持有序状态,因此我们可以推断出右半部分是有序的

这也是为什么在这种情况下,我们可以安全地在右半部分进行查找,前提是目标值target在右半部分的范围内。反之,如果目标值不在右半部分的范围内,那么就去左半部分继续搜索。

你的理解完全正确!这种判断旋转数组中有序部分的方法,是解决这类问题的关键。😊

为什么这一部分代码片段if (nums[mid] < target && target <= nums[right]),如果使用判断条件if (nums[mid] <= target && target < nums[right])会得到错误的答案?

这个问题的核心在于边界条件的不同处理导致的结果差异。让我们仔细分析一下这两个条件的区别,以及为什么会得到不同的答案。

代码片段解释

if (nums[mid] < target && target <= nums[right])

条件比较

  1. 原条件if (nums[mid] < target && target <= nums[right])
  2. 错误条件if (nums[mid] <= target && target < nums[right])

原条件的含义:if (nums[mid] < target && target <= nums[right])

这个条件的意思是:

  • nums[mid] < target:目标值 target 要比 nums[mid] 大。
  • target <= nums[right]:目标值 target 小于或等于 nums[right]

该条件涵盖了目标值在右半部分有序区间内的情况,包括target等于nums[right]的情况。例如,如果右半部分的元素是[1, 2, 3, 4, 5],而target = 5,这个条件会成功匹配到5

错误条件的含义:if (nums[mid] <= target && target < nums[right])

这个条件的意思是:

  • nums[mid] <= target:目标值 target 可以等于 nums[mid]
  • target < nums[right]:目标值 target 必须严格小于 nums[right]

这个条件的一个问题是,当目标值等于nums[right]时,不会满足条件,即使target在右半部分有序区间内。例如,如果右半部分的元素是[1, 2, 3, 4, 5],而target = 5,因为5并不小于nums[right] = 5,这个条件将无法匹配到5

为什么使用错误条件会得到错误答案?

在旋转排序数组中,我们必须精确判断目标值是否在有序区间内。如果使用错误条件 if (nums[mid] <= target && target < nums[right]),就会漏掉当目标值等于右边界元素的情况,导致无法找到目标值,返回错误的结果(如返回-1)。

举个例子帮助理解

假设数组是[4, 5, 6, 7, 0, 1, 2]target = 2,那么:

  • nums[mid] 可能是0nums[right]2
  • 按照原条件 if (nums[mid] < target && target <= nums[right])
    • 0 < 2为真,2 <= 2也为真,条件成立,因此可以在右半部分继续查找。
  • 按照错误条件 if (nums[mid] <= target && target < nums[right])
    • 0 <= 2为真,但是2 < 2为假,因此条件不成立,会错误地调整查找区间。

总结

原条件 if (nums[mid] < target && target <= nums[right]) 保证了目标值即使等于右边界元素 nums[right] 时,仍然可以正确查找到。而错误条件 if (nums[mid] <= target && target < nums[right]) 会遗漏目标值等于右边界的情况,从而导致错误答案。

相关文章:

Leetcode 搜索旋转排序数组

这段代码是用于解决LeetCode第33题“搜索旋转排序数组”的Java解法。以下是对该算法思想的中文解释&#xff1a; 算法思想 二分查找的基本思路&#xff1a; 由于数组是部分有序的&#xff08;被旋转过&#xff09;&#xff0c;我们可以利用二分查找的思想&#xff0c;逐步缩小…...

Spring Task—定时任务

Spring Task 是 Spring 提供的一种轻量级定时任务调度功能&#xff0c;内置在 Spring 框架中。与 Quartz 等重量级调度框架相比&#xff0c;Spring Task 使用简便&#xff0c;无需额外依赖&#xff0c;适合在简单的调度任务场景中使用。通过注解配置方式&#xff0c;开发者可以…...

Spring Boot 应用开发概述

目录 Spring Boot 应用开发概述 Spring Boot 的核心特性 Spring Boot 的开发模式 Spring Boot 在企业应用开发中的优势 结论 Spring Boot 应用开发概述 Spring Boot 是由 Pivotal 团队开发的一个框架&#xff0c;基于 Spring 框架&#xff0c;旨在简化和加速基于 Spring …...

Chrome谷歌浏览器加载ActiveX控件之allWebDesktop控件介绍

背景 allWebDesktop控件是一款方便用户在线打开各类文档的OA办公控件。它设计比较轻巧&#xff0c;充分利用计算机程序资源打开文档&#xff0c;并将程序窗口嵌入到allWebDesktop控件区域内&#xff0c;从而实现浏览器内打开各类文档效果。 allWebPlugin中间件是一款为用户提供…...

GitHub Star 数量前 5 的开源应用程序生成器

欢迎来的 GitHub Star 数量排名系列文章的第 7 篇——最受欢迎的应用程序生成器。 之前我们已经详细探讨过&#xff1a;在 GitHub 上最受欢迎的——无代码工具、低代码项目、内部工具、CRUD项目、自部署项目和 Airtable 开源替代品。累计超过 50 个优质项目&#xff01;&#…...

DBC文件当中新建CANFD等类型的报文

同学最近有添加CANFD报文的需求&#xff0c;需要用到CANFD类型报文的DBC文件&#xff0c;这下就难住我了&#xff0c;我之前用的DBC文件只有“CAN Standard”“CAN Extended”两种类型&#xff0c;压根没见过FD的。 后来他找到了项目之前的DBC&#xff0c;打开来看&#xff0c…...

基于SpringBoot的房地产销售管理系统【附源码】

基于SpringBoot的房地产销售管理系统&#xff08;源码L文说明文档&#xff09; 目录 4 系统设计 4.1用户登录功能的详细实现 4.2管理员权限的功能实现 4.2.1客户信息管理功能的详细实现 4.2.2房产管理功能的详细实现 4.2.3预约看房功能的详细实现 4.2.4论…...

圆点虚线 Android

参考 https://blog.csdn.net/l_o_s/article/details/73550876 <com.xxx.wwww.weight.PointDividerViewandroid:layout_width"match_parent"android:layout_height"wrap_content"app:PDbackgroundColor"color/white"app:dotColor"color/…...

贵州鑫宏远农业-始终致力于推动现代农业的科技创新与发展

贵州鑫宏远农业科技有限公司&#xff0c;是一家在高科技农业领域深耕细作、锐意进取的企业。自成立以来&#xff0c;我们始终致力于推动现代农业的科技创新与发展&#xff0c;业务全面覆盖农业科学研发、组织培养生产、专业育苗培植、半成品及成品精细化养护、市场销售以及全方…...

程序员做销售,从代码到客户的逆袭之路

大家好&#xff0c;我是小悟。 在这个互联网风起云涌、技术迭代日新月异的时代&#xff0c;“跨界”已然成为一种新潮流。就好似那从天而降的大侠&#xff0c;一不小心就可能横跨了数个充满奇遇与挑战的领域。 想象一下&#xff0c;一个平日里只跟代码打交道的程序员&#xf…...

Flink CDC系列之:理解学习Kubernetes模式

Flink CDC系列之&#xff1a;理解学习Kubernetes模式 准备会话模式启动会话集群设置 Flink CDC提交 Flink CDC Job Kubernetes 是一种流行的容器编排系统&#xff0c;用于自动化计算机应用程序的部署、扩展和管理。Flink 的原生 Kubernetes 集成允许您直接在正在运行的 Kuberne…...

git合并相关操作详解

在使用Git进行分支管理时,合并(merge)操作是非常常见的。下面是Git合并相关的详细步骤和一些常见的场景及注意事项。 一、 基本合并操作 假设我们有两个分支:main 和 feature,希望将 feature 合并到 main 上。 切换到目标分支 首先需要切换到你想合并到的分支。例如,切…...

前端经典【面试题】持续更新HTML、CSS、JS、VUE、FLUTTER、性能优化等

HTML/CSS 面试题 什么是语义化 HTML&#xff1f; 说明&#xff1a;语义化 HTML 使用 HTML 标签来描述内容的含义&#xff0c;而不仅仅是其外观。使用语义化标签可以提高可读性和可访问性&#xff0c;并对 SEO 友好。示例&#xff1a; <header><h1>网站标题</h1&…...

【Linux知识】linux磁盘管理深入了解

文章目录 常见磁盘管理命令行磁盘分区NASNAS 磁盘挂载&#x1f510; 如何设置NAS设备的访问权限&#xff1f; Mkfs&#x1f9d0; mkfs 命令支持哪些文件系统类型&#xff1f; Mount&#x1f511; 在Linux中&#xff0c;如何安全地卸载挂载的文件系统&#xff1f; 常见磁盘管理命…...

Qt Essential Classes

目录 QVariant QFlags QRandomGenerator 经典的Qt容器 QVector QList QMap QMultiMap QSet QHash QVariant 同std::variant是一样的&#xff0c;他是一个更加高级的union。在一个时间下&#xff0c;它虽然实际上只能是一种类型&#xff0c;但是一个variant可以hold住…...

小小猫棒onu替换家用光猫,薅运营商带宽羊毛,突破1000M

小小猫棒onu 一、总体步骤 1 记录原来光猫信息 主要包括SN&#xff0c;ploam密码&#xff0c;loid、loid密码、 mac、上网的vlan id等 一般gpon采用SN、ploam密码、SNploam密码三种中的一种认证方式 一般Epon采用loid&#xff08;逻辑id&#xff09;、mac、loid mac三种中…...

软件测试学习笔记丨Selenium学习笔记:css定位

本文转自测试人社区&#xff0c;原文链接&#xff1a;https://ceshiren.com/t/topic/22511 本文为霍格沃兹测试开发学社的学习经历分享&#xff0c;写出来分享给大家&#xff0c;希望有志同道合的小伙伴可以一起交流技术&#xff0c;一起进步~ 说明&#xff1a;本篇博客基于sel…...

python数据处理常用操作

数据处理是机器学习中非常重要的一步&#xff0c;以下是一些常用的操作和示例代码&#xff1a; 1. 数据清洗 处理缺失值&#xff1a; import pandas as pd# 读取数据 df pd.read_csv(data.csv)# 删除缺失值 df.dropna(inplaceTrue)# 用均值填充缺失值 df.fillna(df.mean(), i…...

解决minio跨域问题

MinIO 支持跨域资源共享(CORS)&#xff0c;允许你配置跨域请求的相关策略。以下是一个基本的CORS配置示例&#xff0c;你可以在MinIO的配置文件&#xff08;例如config.json&#xff09;中设置这些策略&#xff1a; 在Linux中 root/.minio 目录下如果没有就新建一个 config.jso…...

python 跳过当前循环

在 Python 中&#xff0c;可以使用 continue 语句来跳过当前循环的剩余部分&#xff0c;并继续下一次循环。continue 语句用于跳过循环体中剩余的语句&#xff0c;并立即开始下一次迭代。 以下是一个简单的示例&#xff0c;演示了如何在 for 循环中使用 continue 语句&#xf…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

stm32G473的flash模式是单bank还是双bank?

今天突然有人stm32G473的flash模式是单bank还是双bank&#xff1f;由于时间太久&#xff0c;我真忘记了。搜搜发现&#xff0c;还真有人和我一样。见下面的链接&#xff1a;https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【SpringBoot】100、SpringBoot中使用自定义注解+AOP实现参数自动解密

在实际项目中,用户注册、登录、修改密码等操作,都涉及到参数传输安全问题。所以我们需要在前端对账户、密码等敏感信息加密传输,在后端接收到数据后能自动解密。 1、引入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

MODBUS TCP转CANopen 技术赋能高效协同作业

在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...