当前位置: 首页 > 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…...

Android Wi-Fi 连接失败日志分析

1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分&#xff1a; 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析&#xff1a; CTR…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

C# 类和继承(抽象类)

抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...

Unit 1 深度强化学习简介

Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库&#xff0c;例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体&#xff0c;比如 SnowballFight、Huggy the Do…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...