【LeetCode热题100】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) 的算法解决此问题。
二.题目难度
中等
三.输入样例
示例 1:
输入:nums = [4,5,6,7,0,1,2], target = 0
输出:4
示例 2:
输入:nums = [4,5,6,7,0,1,2], target = 3
输出:-1
示例 3:
输入:nums = [1], target = 0
输出:-1
提示:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
nums 中的每个值都 独一无二
题目数据保证 nums 在预先未知的某个下标上进行了旋转
-104 <= target <= 104
四.解题思路
首先二分递归查找到旋转边界。
而后将target和数组末位置比较,决定是在左右哪个区间二分。
五.代码实现
class Solution {
public:int search(vector<int>& nums, int target) {int index = dfs(nums, 0, nums.size() - 1);int l;int r;if (target > *nums.rbegin()) {l = 0;r = index;} else {l = index + 1;r = nums.size() - 1;}while (l <= r) {int m = (l + r) / 2;if (nums[m] == target)return m;if (nums[m] > target) {r = m - 1;} elsel = m + 1;}return -1;}int dfs(vector<int>& nums, int left, int right) {if (left > right || (left + right) / 2 + 1 >= nums.size())return -1;if (nums[(left + right) / 2] > nums[(left + right) / 2 + 1])return (left + right) / 2;int a = dfs(nums, left, (left + right) / 2 - 1);int b = dfs(nums, (left + right) / 2 + 1, right);if (a != -1)return a;if (b != -1)return b;return -1;}
};
六.题目总结
–
相关文章:
【LeetCode热题100】33. 搜索旋转排序数组(二分)
一.题目要求 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], …...
基于Leaflet.js的Marker闪烁特效的实现-模拟预警
目录 前言 一、闪烁组件 1、关于leaflet-icon-pulse 2、 使用leaflet-icon-pulse 3、方法及参数简介 二、闪烁实例开发 1、创建网页 2、Marker闪烁设置 3、实际效果 三、总结 前言 在一些地质灾害或者应急情况当中,或者热门预测当中。我们需要基于时空位置来…...
Vue-05
v-model 应用于其他表单元素 常见的表单元素都可以用v-model绑定关联 → 快速获取或设置表单元素的值 它会根据控件类型自动选取正确的方法来更新元素 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name…...
Mongodb中一个小巧的数据更新命令$inc
学习mongodb,体会mongodb的每一个使用细节,欢迎阅读威赞的文章。这是威赞发布的第55篇mongodb技术文章,欢迎浏览本专栏威赞发布的其他文章。 $inc是一个很小巧的命令。说它小巧,一个是因为短,只有三个字符。另一个是说…...
Java基于SpringBoot+Vue的专家医院预约挂号系统,附源码
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 🍅文末获取源码联系🍅 👇🏻 精彩专栏推荐订阅👇…...
STM32一个地址未对齐引起的 HardFault 异常
1. 概述 客户在使用 STM32G070 的时候,KEIL MDK 为编译工具,当编译优化选项设置为Level0 的时候,程序会出现 Hard Fault 异常,而当编译优化选项设置为 Level1 的时候,则程序运行正常。表面上看,这似乎是 K…...
spring事务那些事
实际工作中还会面临千奇百怪的问题,看下面返个例子(注意MySql数据库测试): //1.hello1Service 调用 hello2Service Transactional(propagation Propagation.REQUIRED,rollbackFor Exception.class) public void doUpdate() {//…...
设计模式深度解析:AI大模型下的策略模式与模板方法模式对比解析
🌈 个人主页:danci_ 🔥 系列专栏:《设计模式》《MYSQL应用》 💪🏻 制定明确可量化的目标,坚持默默的做事。 策略模式与模板方法模式对比解析 文章目录 🌟引言🌟Part 1:…...
贪婪算法python实现
贪婪算法(Greedy Algorithm)是一种解决问题的策略,它基于一种贪心的思想:在每一步选择中都采取当前状态下最好或最优的选择,从而希望最终能够得到全局最优解。 其核心思想可以简单概括为“当前局部最优选择”ÿ…...
(一)基于IDEA的JAVA基础12
一维数组 为什么使用数组: 当我们需要存储一系列数据的时候,就需要用到数组,如果不使用数组,我们就要需要一个一个的去声明变量,这样浪费内存空间,同时效率低下。 什么是数组: 数组本身就是一个变量,只…...
vue3中封装table表格
封装实例useTable import {ref } from vue export function useTable(api) {const data = ref([])const refre...
【Redis】Redis的使用
登录redis [roottest2 ~]# redis-cli 127.0.0.1:6379> 或[roottest2 ~]# redis-cli -h 192.168.67.12 -p 6379 192.168.67.12:6379> redis-benchmark 测试工具 redis-benchmark 是官方自带的Redis性能测试工具,可以有效的测试Redis服务的性能 基本的测试语…...
【机器学习300问】60、图像分类任务中,训练数据不足会带来什么问题?如何缓解图像数据不足带来的问题?
在机器学习中,绝大部分模型都需要大量的数据进行训练和学习(包括有监督学习和无监督学习),然而在实际应用中经常会遇到训练数据不足的问题。就比如图像分类这样的计算机视觉任务,确实依赖于大规模且多样化的训练数据以…...
鸿蒙内核源码分析 (内存管理篇) | 虚拟内存全景图是怎样的
初始化整个内存 OsSysMemInitOsMainmain从 main() 跟踪可看内存部分初始化是在 OsSysMemInit() 中完成的。 UINT32 OsSysMemInit(VOID) {STATUS_T ret;OsKSpaceInit();//内核空间初始化ret OsKHeapInit(OS_KHEAP_BLOCK_SIZE);// 内核动态内存初始化 512K if (ret ! LOS_OK…...
基于深度学习的电动自行车头盔佩戴检测系统
文章目录 1. 文档说明2. 运行环境说明2.1 硬件配置2.2 软件配置2.3 程序依赖库 3. 基本环境配置3.1 软件安装3.1.1 集成开发环境安装与配置3.1.2 数据库安装与配置3.1.3 编程语言安装3.1.4 CUDA和cuDNN安装与配置3.1.5 机器学习库安装 3.2 依赖库安装 4. 运行程序资源下载地 1.…...
GO - 泛型编程
go - 泛型编程 介绍 泛型即开发过程中编写适用于所有类型的模板,只有在具体使用的时候才能确定其真正的类型。随着Go 1.18版本的发布,泛型正式成为了Go语言的一部分。 在编写代码时,我们经常会遇到需要处理不同类型的数据的情况。传统上&am…...
TouchableOpacity和TouchableWithoutFeedback区别
TouchableOpacity和TouchableWithoutFeedback都是React Native中定义的可触摸组件,但它们之间有一些区别: 点击效果:TouchableOpacity在被按下时会有一个透明度变化的点击效果,而TouchableWithoutFeedback则没有点击效果。 子组…...
MySQL EXISTS 语句和IN语句有啥区别
在 MySQL 中,EXISTS 和 IN 是用于子查询的两种不同方式,它们有一些区别: 1. **IN 语句**: - IN 子句用于在 WHERE 子句中指定多个值,并检查主查询中的某个列是否在子查询返回的结果集中。 - IN 子句适用于子查询…...
Java集合体系面试题
1. Java中有哪些主要的集合接口? 答案:Java中主要的集合接口有Collection、List、Set、Queue和Map。 2. 请解释List和Set之间的主要区别。 答案:List和Set的主要区别在于元素的顺序和唯一性。List是有序的集合,允许存储重复的元…...
React-2-useState-获取DOM-组件通信
一.useState useState 是一个 React Hook(函数),它允许我们向组件添加一个状态变量, 从而控制影响组件的渲染结果 本质:和普通JS变量不同的是,状态变量一旦发生变化组件的视图UI也会跟着变化**(数据驱动视…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
Leetcode 3576. Transform Array to All Equal Elements
Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接:3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
