【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也会跟着变化**(数据驱动视…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】
1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件(System Property Definition File),用于声明和管理 Bluetooth 模块相…...
Ascend NPU上适配Step-Audio模型
1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统,支持多语言对话(如 中文,英文,日语),语音情感(如 开心,悲伤)&#x…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈
在日常iOS开发过程中,性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期,开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发,但背后往往隐藏着系统资源调度不当…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...
