Leetcode33.搜索旋转排列数组

news/2024/4/24 23:41:36/

搜索旋转排列数组

    • 一、题目描述:
    • 二、解决思路和代码
      • 1. 解决思路
      • 2. 代码

一、题目描述:

整数数组 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. 示例 1:

    • 输入:nums = [4,5,6,7,0,1,2], target = 0
    • 输出:4
  2. 示例 2:

    • 输入:nums = [4,5,6,7,0,1,2], target = 3
    • 输出:-1
  3. 示例 3:

    • 输入:nums = [1], target = 0
    • 输出:-1
  • 提示:
    • 1 ≤ n u m s . l e n g t h ≤ 5000 1 \leq nums.length \leq 5000 1nums.length5000
    • − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 \leq nums[i] \leq 10^4 104nums[i]104
    • nums 中的每个值都 独一无二
    • − 1 0 4 ≤ t a r g e t ≤ 1 0 4 -10^4 \leq target \leq 10^4 104target104

二、解决思路和代码

1. 解决思路

  • 分析:分两步解决:分割,查找,这两个步骤都使用二分查找的方法
    • 分割:将旋转数组分割为两个递增的数组【二分查找索引】
    • 查找:对比 target 与 nums[0] 两个数值的大小,确定在哪一个递增数组中进行查找【二分查找目标值】

2. 代码

from typing import *
class Solution:def getIndex(self, nums:List[int]) -> int:left, right = 0, len(nums)-1while left<=right:mid = (left+right)//2if nums[mid]>nums[left] and nums[mid]>nums[right]:left = midelif nums[mid]<nums[left] and nums[mid]<nums[right]:right = midelse:return left if nums[left]<nums[right] else rightreturn -1def binarySearch(self,nums:List[int], target:int, start:int, end:int) -> int:while start<=end:mid = (start+end)//2if nums[mid]<target:start = mid+1elif nums[mid]>target:end = mid-1else:return midreturn -1def search(self, nums: List[int], target: int) -> int:start = self.getIndex(nums)if start == -1 or start==0:return self.binarySearch(nums,target,0,len(nums)-1)if target>=nums[0]:return self.binarySearch(nums,target,0,start-1)else:return self.binarySearch(nums,target,start,len(nums)-1)

http://www.ppmy.cn/news/48123.html

相关文章

【Unity VR开发】结合VRTK4.0:添加遮蔽追踪器

语录&#xff1a; 恋爱应该是双方扶持对方共同完成自己的目标&#xff0c;而不是虚幻的思想、肤浅的物质、和纸醉金迷的生活。 前言&#xff1a; 遮蔽追踪器&#xff08;Trackers.ObscuranceTracker&#xff09;是基于游戏对象存在或不可见之间切换对象的状态&#xff0c;从而遮…

Ajax超详解(新手入门指南)

文章目录 1. AJAX简介2. 前后端交互3. XHR3.1 XMLHttpRequest对象3.2 获取模拟的后端数据3.3 获取网络数据3.4 使用json-server模拟服务器3.4.1 安装node.js3.4.2 安装并使用json-server 3.5 常见的请求方式3.5.1 GET请求3.5.2 POST请求3.5.3 PUT请求3.5.4 PATCH请求3.5.5 DELE…

面试题30天打卡-day10

1、String 和 StringBuffer、StringBuilder 的区别是什么&#xff1f; String、StringBuffer、StringBuilder主要的区别在于执行效率和线程安全上。 String&#xff1a;String字符串常量&#xff0c;意味着它是不可变的&#xff0c;导致每次对String都会生成新的String对象&a…

网络工程师经常搞混的路由策略和策略路由,两者到底有啥区别?

当涉及到网络路由时&#xff0c;两个术语经常被混淆&#xff1a;策略路由和路由策略。虽然这些术语听起来很相似&#xff0c;但它们实际上有着不同的含义和用途。在本文中&#xff0c;我们将详细介绍这两个术语的区别和应用。 一、路由策略 路由策略是指一组规则&#xff0c;用…

十大排序算法之插入排序、希尔排序、选择排序

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【数据结构初阶&#xff08;C实现&#xff09;】 本篇主要讲解八大排序算法中的三种排序&#xff0c;分别是&#xff1a;插入排序、希尔排…

高并发的程序设计-系统设计层面

高并发的程序设计-系统设计层面 目录概述需求&#xff1a; 设计思路实现思路分析1.主要指标二、处理高并发的方案 参考资料和推荐阅读 Survive by day and develop by night. talk for import biz , show your perfect code,full busy&#xff0c;skip hardness,make a better …

【C++类和对象】类和对象(上) {初识面向对象,类的引入,类的定义,类的访问限定符,封装,类的作用域,类的实例化,类对象模型,this指针}

一、面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题的步骤&#xff0c;通过函数调用逐步解决问题。 C是基于面向对象的&#xff0c;关注的是对象&#xff0c;将一件事情拆分成不同的对象&#xff0c;靠对象之间的交互完成。…

如何将项目提交到别人的仓库

大纲&#xff1a; 1、在gitee中克隆(clone)别人仓库的代码。 首先&#xff0c;进入别人的仓库&#xff0c;点击 克隆/下载 2、在你存放项目的文件夹下克隆你刚刚复制的代码 &#xff08;右键点击Git Clone即可&#xff09; 点击OK 就开始克隆了 克隆成功之后&#xff0c;文件上…

springboot+vue准妈妈孕期交流平台(源码+文档)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的准妈妈孕期交流平台。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 &#x1f495;&#x1f495;作者&#xff1a;…

【Spring Boot】SpringBoot 优雅整合Swagger Api 自动生成文档

文章目录 前言一、添加 Swagger 依赖二、创建接口类三、添加 Swagger 配置类四、访问 Swagger 页面五、整合一个更友好的UI接口文档 Knife4j1、添加 Knife4j 依赖2、添加 Knife4j 配置类3、访问 Knife4j 页面 总结 前言 Swagger 是一套 RESTful API 文档生成工具&#xff0c;可…

ChatGPT原理详解+实操

言 ChatGPT已近火了快大半年了&#xff0c;从去年刚出来的时候小编就关注了一下&#xff0c;也具体的使用过&#xff0c;然后就惊为天人&#xff0c;再然后就没有然后了&#xff0c;因为小编那段时间沉迷于AIGC了。ChatGPT今年开年后更是火的一塌糊涂&#xff0c;无论是行业内…

一流棒球特色学校应该具备什么条件·棒球1号位

随着人们生活水平的提高和健康意识的增强&#xff0c;越来越多的人开始关注体育运动的健康和乐趣。而棒球作为一项全身性、协调性和技术性都极高的运动&#xff0c;受到了越来越多人的喜爱和追捧。为了满足人们对于棒球运动的需求&#xff0c;棒球特色学校应运而生。那么&#…

一文搞懂文件下载·读取漏洞

一文搞懂文件下载读取漏洞 1.概述2.利用思路3.常见文件WindowsLinux 4.不安全的文件下载绕过手法5.修复建议 1.概述 文件下载功能在很多web系统上都会出现&#xff0c;一般我们当点击下载链接&#xff0c;便会向后台发送一个下载请求&#xff0c;一般这个请求会包含一个需要下…

一名合格的亚马逊运营,从早到晚都在做什么?

最近东哥分享了很多关于亚马逊话题的文章&#xff0c;发现有很多小伙伴很好奇亚马逊运营的事&#xff0c;很多人都说很想知道一名合格的亚马逊运营每天都需要干什么&#xff0c;那今天东哥就拿我们自己团队的亚马逊运营来跟大家聊一聊。 亚马逊运营从早到晚都干了些什么活&…

微信小程序自定义组件:组件间通讯

前言 略 组件间通信 组件间的基本通信方式有以下几种&#xff1a; WXML 数据绑定&#xff1a;用于父组件向子组件的指定属性设置数据&#xff0c;仅能设置 JSON 兼容数据&#xff08;自基础库版本 2.0.9 开始&#xff0c;还可以在数据中包含函数&#xff09;。具体在 组件模…

Python如何使用和配置Anaconda入门

1、Anaconda介绍 Anaconda 是一款广泛使用的Python和R语言开发环境&#xff0c;集成了许多常用的科学计算和数据分析库。它包括conda、Python解释器以及大量有用的库和工具&#xff0c;使得您可以更轻松地搭建Python和R的开发环境。此外&#xff0c;Anaconda 还提供了一个简单…

网络编程及项目思路

计算机和计算机之间通过网络进行数据传输 常见的软件架构&#xff1a; C/S:客户端/服务器 画面可以做的非常精美&#xff0c;用户体验好需要开发客户端&#xff0c;也需要开发服务端用户需要下载和更新的时候太麻烦 B/S:浏览器/服务器 不需要开发客户端&#xff0c;只需要…

车企围攻整车OS,这张“新王牌”怎么打?

今年2月23日&#xff0c;梅赛德斯--奔驰发布了打造自有操作系统MB.OS的具体计划&#xff0c;该操作系统将在本年代中期随全新梅赛德斯-奔驰模块化架构&#xff08;MMA&#xff09;平台推出&#xff0c;预计2025年用户将能体验到它的强大功能。 据悉&#xff0c;基于覆盖芯片到…

Linux_红帽8学习笔记分享_5

Linux_红帽8学习笔记分享_5 文章目录 Linux_红帽8学习笔记分享_51. UMASK反掩码1.1如何查看反掩码umask1.2 UMASK反掩码的作用1.2.1对于目录来说1.2.2对于文件来说 1.3如何修改UMASK反掩码1.4普通用户反掩码的测试 2.whereis的使用3. SUID权限弥补(主要针对文件,所有者执行位变…

C++---状态压缩dp---炮兵阵地(每日一道算法2023.4.17)

注意事项&#xff1a; 本题为"状态压缩dp—蒙德里安的梦想"和"状态压缩dp—小国王"和"状态压缩dp—玉米田"的近似题&#xff0c;建议先阅读这三篇文章并理解。 题目&#xff1a; 司令部的将军们打算在 NM 的网格地图上部署他们的炮兵部队。 一个…