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

Leetcode33 搜索旋转排序数组

 

 题解:

/*** 旋转排序数组可分为N1 + N2两个部分,如:[4,5,6,7,1,2,3],N1为[4,5,6,7],N2为[1,2,3]** 必然满足以下两个条件:* 1. N1和N2都是分别递增的;* 2. N1中的所有元素大于N2中的所有元素;** 以上两个条件可推出:nums[0]是N1中最小的数,即nums[0] > N2中的所有元素** 而mid不是在N1内就是在N2内,如果在N1内,则在N1内使用二分查找,否则在N2内使用二分查找* 所以:如果nums[0] <= nums[mid],即mid落在了N1内,则[0, mid]肯定是有序的*       否则mid落在了N2内,则[mid, n)肯定是有序的**/
if (nums[0] <= nums[mid]) {// 左半边有序
} else {// 右半边有序
}

先判断nums[mid]是在旋转数组的左半边,还是右半边;

如果在左半边然后使用target和nums[0]和nums[mid]作比较,target处于[0,mid]中间,right = mid - 1; else left = mid + 1;

如果在右半边,使用target和nums[mid] nums[nums.length-1]作比较,target处于[mid,nums[nums.length-1]], left = mid + 1,否则right = mid-1

代码

public int search(int[] nums, int target) {if(nums.length == 0){return -1;    }int left = 0, right = nums.length - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target){return mid;}//左半边有序,在左半边使用二分查找if(nums[mid] >= nums[0]){if(nums[0] <= target && target < nums[mid]){ //target处于[0,mid),向左移动mid            right = mid - 1;}else{left = mid + 1;}}//右半边有序,在右半边使用二分查找else{if(nums[mid] < target && target <= nums[nums.length - 1]){left = mid + 1;}else{right = mid - 1;}}}return -1;}

相关文章:

Leetcode33 搜索旋转排序数组

题解&#xff1a; /*** 旋转排序数组可分为N1 N2两个部分&#xff0c;如&#xff1a;[4,5,6,7,1,2,3]&#xff0c;N1为[4,5,6,7]&#xff0c;N2为[1,2,3]** 必然满足以下两个条件&#xff1a;* 1. N1和N2都是分别递增的&#xff1b;* 2. N1中的所有元素大于N2中的所有元素;** …...

docker 第一章

目录 1.安装 docker 2.镜像、容器 3.总结 1.安装 docker 2.镜像、容器 3.总结 容器在 linux 上的本机运行&#xff0c;与其他容器共享主机的内核。它运行的是一个独立的进程&#xff0c;不占用其他任何可执行文件的内存&#xff0c;非常轻量级。...

注册中心 —— SpringCloud Netflix Eureka

Eureka 简介 Eureka 是一个基于 REST 的服务发现组件&#xff0c;SpringCloud 将它集成在其子项目 spring-cloud-netflix 中&#xff0c;以实现 SpringCloud 的服务注册与发现&#xff0c;同时提供了负载均衡、故障转移等能力&#xff0c;目前 Eureka2.0 已经不再维护&#xf…...

2023年国赛数学建模思路 - 案例:异常检测

文章目录 赛题思路一、简介 -- 关于异常检测异常检测监督学习 二、异常检测算法2. 箱线图分析3. 基于距离/密度4. 基于划分思想 建模资料 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 一、简介 – 关于异常…...

⛳ Java 反射

目录 ⛳ Java 反射&#x1f3a8; 一、反射概述**&#x1f383; 使用反射的前提条件: **&#x1f3b2; 类正常加载过程如下图&#xff1a;反射优缺点&#xff1a;&#x1f9f8; Java反射机制提供的功能: **&#x1f945; 反射主要API** &#x1f3ed; 二、反射的使用&#x1f3a…...

Android 13 像Settings一样开启关闭深色模式

一.背景 由于客户定制的Settings需要开启关闭深色模式,所以需要自己调用开启关闭深色模式 二.前提条件 首先应用肯定要是系统应用,并且导入framework.jar包,具体可以参考: Android 应用自动开启辅助(无障碍)功能并使用辅助(无障碍)功能_android 自动开启无障碍服务_龚礼鹏…...

微服务实战项目-学成在线-项目优化(redis缓存优化)

微服务实战项目-学成在线-项目优化(redis缓存优化) 1 优化需求 视频播放页面用户未登录也可以访问&#xff0c;当用户观看试学课程时需要请求服务端查询数据&#xff0c;接口如下&#xff1a; 1、根据课程id查询课程信息。 2、根据文件id查询视频信息。 这些接口在用户未认…...

IDEA 找不到项目 ‘org.springframework.boot:spring-boot-starter-parent:3.1.2‘

找不到项目 ‘org.springframework.boot:spring-boot-starter-parent:2.6.7’ 这个问题主要是因为ide的缓存导致的&#xff0c;我们直接清理缓存并重启ide 重启之后ide会对pom文件进行编排索引完成之后问题就没有了...

thinkphp开发的在线学习培训考试模拟考试做题练习系统带商城功能证书管理课程系统

thinkphp开发的在线学习培训考试模拟考试做题练习系统带商城功能证书管理课程系统 1、做题界面 2、前端UI的展示 3、带商城购物功能...

Android 应用冷启动优化

冷启动相关概念 应用启动概念 冷启动&#xff1a;首次打开app或者app彻底销毁后再次打开app&#xff08;开关机后&#xff09;&#xff0c;这也是我们进行启动速度优化的主要方向。热启动&#xff1a;应用运行中按home键再打开应用。温启动&#xff1a;介于两者之间&#xff…...

538页21万字数字政府智慧政务大数据云平台项目建设方案WORD

导读&#xff1a;原文《538页21万字数字政府智慧政务大数据云平台项目建设方案WORD》&#xff08;获取来源见文尾&#xff09;&#xff0c;本文精选其中精华及架构部分&#xff0c;逻辑清晰、内容完整&#xff0c;为快速形成售前方案提供参考。 根据业务的不同属性&#xff0c…...

进程间通信——信号

信号的概念 信号是 Linux进程间通信的最古老的方式之一&#xff0c;是事件发生时对进程的通知机制&#xff0c;有时也称之为软件中断&#xff0c;它是在软件层次上对中断机制的一种模拟&#xff0c;是一种异步通信的方式。信号可以导致一个正在运行的进程被另一个正在运行的异…...

PAT 1039 Course List for Student

个人学习记录&#xff0c;代码难免不尽人意。 Zhejiang University has 40000 students and provides 2500 courses. Now given the student name lists of all the courses, you are supposed to output the registered course list for each student who comes for a query. …...

【Sklearn】基于决策树算法的数据分类预测(Excel可直接替换数据)

【Sklearn】基于决策树算法的数据分类预测(Excel可直接替换数据) 1.模型原理1.1 模型原理1.2 数学模型2.模型参数3.文件结构4.Excel数据5.下载地址6.完整代码7.运行结果1.模型原理 决策树是一种基于树状结构的分类和回归模型,它通过一系列的决策规则来将数据划分为不同的类…...

并发编程4:Java 中的并发基础构建模块

目录 1、同步容器类 1.1 - 同步容器类的问题 1.2 - 迭代和容器加锁 2、并发容器类 2.1 - ConcurrentHashMap 类 2.2 - CopyOnWriteArrayList 类 3、阻塞队列和生产者-消费者模式 3.1 - 串行线程封闭 4、阻塞方法与中断方法 5、同步工具类 5.1 - 闭锁 -> CountDow…...

Vue-10.集成(.editorconfig、.eslintrc.js、.prettierrc)

介绍 同时使用 .editorconfig、.prettierrc 和 .eslintrc.js 是很常见的做法&#xff0c;因为它们可以在不同层面上帮助确保代码的格式一致性和质量。这种组合可以在开发过程中提供全面的代码维护和质量保证。然而&#xff0c;这也可能增加一些复杂性&#xff0c;需要谨慎配置…...

PHP-FPM进程排查

1、查看php-fpm的进程个数 ps -ef |grep "php-fpm"|grep "pool"|wc -l2、查看每个php-fpm占用的内存大小 ps -ylC php-fpm --sort:rss3.查看PHP-FPM在你的机器上的平均内存占用 ps --no-headers -o "rss,cmd" -C php-fpm | awk { sum$1 } END…...

PHP-MD5注入

0x00 前言 有些零散的知识未曾关注过&#xff0c;偶然捡起反而更加欢喜。 0x01 md5 注入绕过 md5函数有两个参数&#xff0c;第一个参数是要进行md5的值&#xff0c;第二个值默认为false&#xff0c;如果为true则返回16位原始二进制格式的字符串。意思就是会将md5后的结果当…...

对redis、redisson、springcache总结

<一> redis-缓存中间件 什么是redis redis是c语言开发的&#xff0c;一个高性能key-value键值对内存数据库&#xff0c;可以用来做数据库、缓存、消息中间件的一种非关系型数据库。 redis数据存储在哪里 内存和磁盘中&#xff0c;但是redis的读写都在内存中&#xff0c;…...

Java基础知识实际应用(学生信息管理系统、猜拳小游戏、打印日历)

一、Java学生信息管理系统 这个系统包含了添加、修改、删除、查询和显示所有学生信息等功能。您可以在此基础上进行修改和完善&#xff0c;以适应您的需求。 import java.util.Scanner;public class StudentManagementSystem {private static Scanner scanner new Scanner(S…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...

《Offer来了:Java面试核心知识点精讲》大纲

文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...