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

【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 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [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、实际效果 三、总结 前言 在一些地质灾害或者应急情况当中&#xff0c;或者热门预测当中。我们需要基于时空位置来…...

Vue-05

v-model 应用于其他表单元素 常见的表单元素都可以用v-model绑定关联 → 快速获取或设置表单元素的值 它会根据控件类型自动选取正确的方法来更新元素 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name…...

Mongodb中一个小巧的数据更新命令$inc

学习mongodb&#xff0c;体会mongodb的每一个使用细节&#xff0c;欢迎阅读威赞的文章。这是威赞发布的第55篇mongodb技术文章&#xff0c;欢迎浏览本专栏威赞发布的其他文章。 $inc是一个很小巧的命令。说它小巧&#xff0c;一个是因为短&#xff0c;只有三个字符。另一个是说…...

Java基于SpringBoot+Vue的专家医院预约挂号系统,附源码

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…...

STM32一个地址未对齐引起的 HardFault 异常

1. 概述 客户在使用 STM32G070 的时候&#xff0c;KEIL MDK 为编译工具&#xff0c;当编译优化选项设置为Level0 的时候&#xff0c;程序会出现 Hard Fault 异常&#xff0c;而当编译优化选项设置为 Level1 的时候&#xff0c;则程序运行正常。表面上看&#xff0c;这似乎是 K…...

spring事务那些事

实际工作中还会面临千奇百怪的问题&#xff0c;看下面返个例子&#xff08;注意MySql数据库测试&#xff09;&#xff1a; //1.hello1Service 调用 hello2Service Transactional(propagation Propagation.REQUIRED,rollbackFor Exception.class) public void doUpdate() {//…...

设计模式深度解析:AI大模型下的策略模式与模板方法模式对比解析

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》《MYSQL应用》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 策略模式与模板方法模式对比解析 文章目录 &#x1f31f;引言&#x1f31f;Part 1:…...

贪婪算法python实现

贪婪算法&#xff08;Greedy Algorithm&#xff09;是一种解决问题的策略&#xff0c;它基于一种贪心的思想&#xff1a;在每一步选择中都采取当前状态下最好或最优的选择&#xff0c;从而希望最终能够得到全局最优解。 其核心思想可以简单概括为“当前局部最优选择”&#xff…...

(一)基于IDEA的JAVA基础12

一维数组 为什么使用数组: 当我们需要存储一系列数据的时候&#xff0c;就需要用到数组&#xff0c;如果不使用数组&#xff0c;我们就要需要一个一个的去声明变量&#xff0c;这样浪费内存空间&#xff0c;同时效率低下。 什么是数组: 数组本身就是一个变量&#xff0c;只…...

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性能测试工具&#xff0c;可以有效的测试Redis服务的性能 基本的测试语…...

【机器学习300问】60、图像分类任务中,训练数据不足会带来什么问题?如何缓解图像数据不足带来的问题?

在机器学习中&#xff0c;绝大部分模型都需要大量的数据进行训练和学习&#xff08;包括有监督学习和无监督学习&#xff09;&#xff0c;然而在实际应用中经常会遇到训练数据不足的问题。就比如图像分类这样的计算机视觉任务&#xff0c;确实依赖于大规模且多样化的训练数据以…...

鸿蒙内核源码分析 (内存管理篇) | 虚拟内存全景图是怎样的

初始化整个内存 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 - 泛型编程 介绍 泛型即开发过程中编写适用于所有类型的模板&#xff0c;只有在具体使用的时候才能确定其真正的类型。随着Go 1.18版本的发布&#xff0c;泛型正式成为了Go语言的一部分。 在编写代码时&#xff0c;我们经常会遇到需要处理不同类型的数据的情况。传统上&am…...

TouchableOpacity和TouchableWithoutFeedback区别

TouchableOpacity和TouchableWithoutFeedback都是React Native中定义的可触摸组件&#xff0c;但它们之间有一些区别&#xff1a; 点击效果&#xff1a;TouchableOpacity在被按下时会有一个透明度变化的点击效果&#xff0c;而TouchableWithoutFeedback则没有点击效果。 子组…...

MySQL EXISTS 语句和IN语句有啥区别

在 MySQL 中&#xff0c;EXISTS 和 IN 是用于子查询的两种不同方式&#xff0c;它们有一些区别&#xff1a; 1. **IN 语句**&#xff1a; - IN 子句用于在 WHERE 子句中指定多个值&#xff0c;并检查主查询中的某个列是否在子查询返回的结果集中。 - IN 子句适用于子查询…...

Java集合体系面试题

1. Java中有哪些主要的集合接口&#xff1f; 答案&#xff1a;Java中主要的集合接口有Collection、List、Set、Queue和Map。 2. 请解释List和Set之间的主要区别。 答案&#xff1a;List和Set的主要区别在于元素的顺序和唯一性。List是有序的集合&#xff0c;允许存储重复的元…...

React-2-useState-获取DOM-组件通信

一.useState useState 是一个 React Hook&#xff08;函数&#xff09;&#xff0c;它允许我们向组件添加一个状态变量, 从而控制影响组件的渲染结果 本质&#xff1a;和普通JS变量不同的是&#xff0c;状态变量一旦发生变化组件的视图UI也会跟着变化**&#xff08;数据驱动视…...

单克隆抗体如何被制备并应用于疾病治疗?

一、什么是单克隆抗体&#xff1f;其与多克隆抗体有何区别&#xff1f;单克隆抗体&#xff08;Monoclonal Antibody&#xff0c;mAb&#xff09;是指由单一B淋巴细胞克隆所产生的高度均一、仅针对某一特定抗原表位进行识别的抗体。这类抗体具有高度特异性。与之相对的是多克隆抗…...

Zotero Reference插件:5个步骤实现PDF文献自动化管理

Zotero Reference插件&#xff1a;5个步骤实现PDF文献自动化管理 【免费下载链接】zotero-reference PDF references add-on for Zotero. 项目地址: https://gitcode.com/gh_mirrors/zo/zotero-reference Zotero Reference是一款革命性的Zotero插件&#xff0c;专门为学…...

PvZ Toolkit完整指南:植物大战僵尸修改器的终极解决方案

PvZ Toolkit完整指南&#xff1a;植物大战僵尸修改器的终极解决方案 【免费下载链接】pvztoolkit 植物大战僵尸 PC 版综合修改器 项目地址: https://gitcode.com/gh_mirrors/pv/pvztoolkit 你是否厌倦了在植物大战僵尸中重复刷资源&#xff1f;是否想体验游戏的全部乐趣…...

DCM模式反激电源各参数逻辑关系

在DCM模式下&#xff0c;变压器本质上是一个“能量存储-释放”的中间体&#xff0c;初级存储的能量必须在每个周期完全释放给次级。1. 变压器初级电感量&#xff08;Lp&#xff09;与最大占空比&#xff08;Dmax​&#xff09;逻辑关系&#xff1a; 在输入电压&#xff08;Vin&…...

读懂 ABAP 调试器里的 ()XVBRP[]:这不是新语法,而是旧式内表加调试器命名表示法的组合

有朋友问我下面这个截图里的变量名是什么语法? 你这张截图里的 ()XVBRP[],结论上并不是一种新的 ABAP 变量声明语法。把它拆开看,更容易理解: XVBRP[] 这一段,核心含义是:XVBRP 是一个带 header line 的旧式内表,而 [] 明确表示你看到的是内表体 table body,不是同名的…...

QMCDecode:让QQ音乐加密文件重获自由的macOS工具

QMCDecode&#xff1a;让QQ音乐加密文件重获自由的macOS工具 【免费下载链接】QMCDecode QQ音乐QMC格式转换为普通格式(qmcflac转flac&#xff0c;qmc0,qmc3转mp3, mflac,mflac0等转flac)&#xff0c;仅支持macOS&#xff0c;可自动识别到QQ音乐下载目录&#xff0c;默认转换结…...

低成本GPU算力玩转大模型编剧:Pixel Script Temple双卡并行部署实操手册

低成本GPU算力玩转大模型编剧&#xff1a;Pixel Script Temple双卡并行部署实操手册 1. 项目概述 Pixel Script Temple是一款专为剧本创作设计的AI工具&#xff0c;基于Qwen2.5-14B-Instruct大模型深度微调而成。它最大的特点是能够在消费级GPU硬件上实现高效运行&#xff0c…...

AI SaaS创业:从0到1打造爆款产品的核心方法论

市场定位与需求验证通过数据分析和用户访谈验证目标市场的真实需求。使用工具如Google Trends、SEMrush分析搜索热度&#xff0c;结合用户调研&#xff08;SurveyMonkey、Typeform&#xff09;明确痛点。避免主观假设&#xff0c;确保产品解决高频、高价值问题。最小可行产品&a…...

SEO推广系统与其他推广渠道的对比

SEO推广系统与其他推广渠道的对比 在现代商业环境中&#xff0c;各种推广渠道层出不穷&#xff0c;其中SEO推广系统和其他传统或新兴的推广渠道各有优劣。本文将从问题分析、原因说明、解决方法、注意事项和实用建议五个方面&#xff0c;深入探讨SEO推广系统与其他推广渠道的对…...

魔兽争霸3现代化修复指南:三步让经典游戏在Windows 10/11完美运行

魔兽争霸3现代化修复指南&#xff1a;三步让经典游戏在Windows 10/11完美运行 【免费下载链接】WarcraftHelper Warcraft III Helper , support 1.20e, 1.24e, 1.26a, 1.27a, 1.27b 项目地址: https://gitcode.com/gh_mirrors/wa/WarcraftHelper 还在为魔兽争霸3在现代电…...