【LeetCode】【算法】33. 搜索旋转排序数组
LeetCode 33. 搜索旋转排序数组
题目描述
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
思路
思路:二分查找法
- 如果
start~mid升序,则前半部分有序;如果mid~end升序,则后半部分有序 - 无论哪部分有序,都要判断target是否在该区间中:
I. target在有序区间中,将start/end移动到有序区间的边界来
II. target不在有序区间中,将start/end移动到有序区间的外面去
代码
class Solution {public int search(int[] nums, int target) {if (nums == null || nums.length == 0) {return -1;}int start = 0;int end = nums.length - 1;int mid;while (start <= end) {mid = start + (end - start) / 2;if (nums[mid] == target) {return mid;}// 如果nums[start]<=nums[mid]说明前半部分是有序的if (nums[start] <= nums[mid]) {if (target >= nums[start] && target < nums[mid]) {end = mid - 1;} else {start = mid + 1;}} else { // 说明后半部分是有序的if (target <= nums[end] && target > nums[mid]) {start = mid + 1;} else {end = mid - 1;}}}return -1;}
}
相关文章:
【LeetCode】【算法】33. 搜索旋转排序数组
LeetCode 33. 搜索旋转排序数组 题目描述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k…...
Python小游戏25——黄金矿工
首先,你需要安装Pygame库。 如果你还没有安装,可以使用以下命令进行安装: 【bash】 pip install pygame 【python】代码展示 import pygame import random # 初始化Pygame pygame.init() # 设置屏幕尺寸 screen_width 800 screen_height 60…...
WPF中Prism框架中 IContainerExtension 和 IRegionManager的作用
在Prism框架中,IContainerExtension和IRegionManager扮演着重要的角色,具体作用如下: IContainerExtension IContainerExtension接口是Prism 7中引入的,用于抽象依赖注入容器的操作。它实现了IContainerProvider和IContainerReg…...
C++实现用户分组--学习
第一步实现:ETL的设计分三部分:数据抽取(Data Extraction)、数据的清洗转换(Data Transformation)、数据的加载(Data Loading). 构建一个数据容器类,其中包含转换后的MNIST手写数据。还实现了一个数据处理程序,该数据处理程序将提…...
鸿蒙华为商城APP案例
模拟器运行效果如下: 鸿蒙版APP-华为商城-演示视频...
回首遥望-C++内存对齐的思考
这一章节主要巩固一下学习C/C时内存对齐相关的内容! 文章目录 什么是内存对齐?为什么要有内存对齐?如何进行内存对齐?致谢: 什么是内存对齐? 这里不提及一堆啰嗦概念,就结合实际出发࿰…...
力扣 LeetCode 704. 二分查找(Day1:数组)
解题思路: 二分查找主要分为[ left , right ]左闭右闭和[ left , right )左闭右开两种 此处采取[ left , right ]左闭右闭写法 注意: 1. right的初始化取值 2. while中取等 3. right mid -1 ; class Solution {public int search(int[] nums, i…...
【Mode Management】AUTOSAR架构下唤醒源检测函数EcuM_CheckWakeup详解
目录 前言 正文 1.AUTOSAR标准描述 1.1 EcuM_CheckWakeup用来干什么 1.2 EcuM_CheckWakeup在哪里被调用 1.3 EcuM_CheckWakeup的使用场景 1.3.1 GPT中断检测唤醒源 1.3.2 EcuM轮询GPT检测唤醒源 1.3.3 ICU中断检测唤醒源 1.3.4 其他 2.AUTOSR工具相关配置 3.唤醒源…...
Zabbix基础信息概述
1.Zabbix概述 Zabbix 是一款能够监控各种网络参数以及服务器健康性和完整性的软件。Zabbix 使用灵活的通知机制,允许用户为几乎任何事件配置基于邮件的告警,这样可以快速反馈服务器的问题。基于已存储的数据,Zabbix 提供了出色的报告和数据可…...
SpringBoot(十二)SpringBoot配置redis
接下来我要实现的webscoket即时聊天中需要使用到redis,我先在项目中配置一下redis。 我这里再windows中做测试,关于redis的安装请移步《Redis(三)Windows系统安装redis》 一:在pom.xml中添加依赖 <!-- springboot redis start --><dependency><grou…...
Pycharm安装
Pycharm安装 返回主目录Pycharm安装1. Pycharm下载PyCharm官网下载地址下载安装包 2. Pycharm安装第一步:双击安装包第二步:进入安装程序第三步:选择安装路径第四步:选择安装选项第五步:安装第六步:完成安装…...
OpenAI大改下代大模型方向,scaling law撞墙?AI社区炸锅了
有研究预计,如果 LLM 保持现在的发展势头,预计在 2028 年左右,已有的数据储量将被全部利用完。届时,基于大数据的大模型的发展将可能放缓甚至陷入停滞。 来自论文《Will we run out of data? Limits of LLM scaling based on hum…...
技术整合与生态构建:Lyft与Mobileye引领自动驾驶新纪元
在科技日新月异的今天,自动驾驶技术正逐渐从科幻电影走进现实生活,成为出行服务领域的一股不可忽视的力量。近日,北美网约车巨头Lyft与自动驾驶技术领先者Mobileye宣布联手合作,共同推动自动驾驶汽车出行服务的广泛商业化进程。此…...
利用huffman树实现对文件A先编码后解码
利用huffman树实现对文件A先编码后解码,范围为ASCII码0-255的值,如何解决特殊符号问题是一个难点,注意应使用unsigned char存储数据,否则ASCII码128-255的值可能会出问题: #define _CRT_SECURE_NO_WARNINGS 1 #includ…...
第三十九章 基于VueCli自定义创建项目
目录 1. 选择创建模式 2. 选择需要的功能 3. 选择历史模式还是哈希模式 4.CSS预处理器 5. 选择ESLint规则 6. 开始创建项目 7. 自定义项目最终结构 1. 选择创建模式 输入创建的项目名,创建项目: 这里选择自定义模式: 2. 选择需要…...
网页web无插件播放器EasyPlayer.js点播播放器遇到视频地址播放不了的现象及措施
在数字媒体时代,视频点播已成为用户获取信息和娱乐的重要方式。EasyPlayer.js作为一款流行的点播播放器,以其强大的功能和易用性受到广泛欢迎。然而,在使用过程中,用户可能会遇到视频地址无法播放的问题,这不仅影响用户…...
LLaMA-Factory学习笔记(1)——采用LORA对大模型进行SFT并采用vLLM部署的全流程
该博客是我根据自己学习过程中的思考与总结来写作的,由于初次学习,可能会有错误或者不足的地方,望批评与指正。 1. 安装 1.1 LLaMA-Factory安装 安装可以参考官方 readme (https://github.com/hiyouga/LLaMA-Factory/blob/main/…...
PHP和Python脚本的性能监测方案
目录 1. 说明 2. PHP脚本性能监测方案 2.1 安装xdebug 2.2 配置xdebug.ini 2.3 命令行与VS Code中使用 - 命令行 - VS Code 2.4 QCacheGrind 浏览 3. Python脚本性能监测方案 3.1 命令行 4. 工具 5.参考 1. 说明 获取我们的脚本程序运行时的指标,对分析…...
C语言实现数据结构之堆
文章目录 堆一. 树概念及结构1. 树的概念2. 树的相关概念3. 树的表示4. 树在实际中的运用(表示文件系统的目录树结构) 二. 二叉树概念及结构1. 概念2. 特殊的二叉树3. 二叉树的性质4. 二叉树的存储结构 三. 二叉树的顺序结构及实现1. 二叉树的顺序结构2.…...
战略共赢 软硬兼备|云途半导体与知从科技达成战略合作
2024年11月5日,江苏云途半导体有限公司(以下简称“云途”或“云途半导体”)与上海知从科技有限公司(以下简称“知从科技”)达成战略合作,共同推动智能汽车领域高端汽车电子应用的开发。 云途半导体与知从科…...
conda相比python好处
Conda 作为 Python 的环境和包管理工具,相比原生 Python 生态(如 pip 虚拟环境)有许多独特优势,尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处: 一、一站式环境管理:…...
深入剖析AI大模型:大模型时代的 Prompt 工程全解析
今天聊的内容,我认为是AI开发里面非常重要的内容。它在AI开发里无处不在,当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗",或者让翻译模型 "将这段合同翻译成商务日语" 时,输入的这句话就是 Prompt。…...
day52 ResNet18 CBAM
在深度学习的旅程中,我们不断探索如何提升模型的性能。今天,我将分享我在 ResNet18 模型中插入 CBAM(Convolutional Block Attention Module)模块,并采用分阶段微调策略的实践过程。通过这个过程,我不仅提升…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
数据链路层的主要功能是什么
数据链路层(OSI模型第2层)的核心功能是在相邻网络节点(如交换机、主机)间提供可靠的数据帧传输服务,主要职责包括: 🔑 核心功能详解: 帧封装与解封装 封装: 将网络层下发…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
VTK如何让部分单位不可见
最近遇到一个需求,需要让一个vtkDataSet中的部分单元不可见,查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行,是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示,主要是最后一个参数,透明度…...
