LeetCode33. 搜索旋转排序数组(2024冬季每日一题 8)

整数数组 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 < = n u m s . l e n g t h < = 5000 1 <= nums.length <= 5000 1<=nums.length<=5000
  • − 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 104<=nums[i]<=104
  • nums 中的每个值都 独一无二
  • 题目数据保证 nums 在预先未知的某个下标上进行了旋转
  • − 1 0 4 < = t a r g e t < = 1 0 4 -10^4 <= target <= 10^4 104<=target<=104

思路:二分查找

  • 二分查找,先判断 target 在左半部分还是右半部分(通过 target 与 数组右半部分最后一个元素比较)
  • 如果在 target 在左边
    • 则判断当前 mid 在左边还是右边
      • 如果当前 mid 在右边(和 target不在同一部分),则 r 指针直接左移
      • 如果当前 mid 在左边(和 target 同一部分),则判断 mid 和 target 的偏差,再移动左右指针
  • 如果当前 target 在右边
    • 则判断当前 mid 在左边还是右边
      • 如果当前 mid 在左边(和 target不在同一部分),则 l 指针直接右移
      • 如果当前 mid 在右边(和 target 同一部分),则判断 mid 和 target 的偏差,再移动左右指针
class Solution {
public:int search(vector<int>& nums, int target) {int n = nums.size();int l = 0, r = n - 1;while(l < r){int mid = (l + r) >> 1;if(target > nums[n - 1]){if(nums[mid] > nums[n-1]){if(target > nums[mid]) l = mid + 1;else r = mid;}else r = mid - 1; }else{if(nums[mid] > nums[n - 1]) l = mid + 1;else{if(target > nums[mid]) l = mid + 1;else r = mid;}}}if(nums[l] == target) return l;else return -1;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/18372.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

Win11专业版Docker安装、配置记录

零&#xff0c;系统环境配置 首先&#xff0c;安装Docker需要系统支持开启硬件虚拟化及Hyper-V功能&#xff0c;所以这里需要Win10/11的专业版&#xff0c;这样才能进行Docker for Windows软件安装。 1&#xff0c;硬件虚拟化 至于如何开启硬件虚拟化&#xff0c;自行百度即…

【Android】线程池的初见

引言 在Android当中根据用途分为主线程与子线程&#xff0c;主线程当中主要处理与界面相关的操作&#xff0c;子线程主要进行耗时操作。除了Thread本身以外&#xff0c;在Android当中还有很多扮演者线程的角色&#xff0c;比如AsyncTask&#xff08; 底层为线程池&#xff0c;…

春秋云镜-2022网鼎杯

flag1 进入网站&#xff0c;发现是wordpress&#xff0c;这种一般都不会有啥直接漏洞&#xff0c;应该是插件漏洞&#xff0c;或者弱口令 fscan扫描ip 好像没扫出啥东西 wp-login进入后台 爆破密码&#xff0c;弱口令admin&#xff0c;123456&#xff0c;之前lazysysadmin好…

js ResizeObserver API

一、ResizeObserver 是什么 ResizeObserver 是一个浏览器提供的 JavaScript API&#xff0c;用于监测一个元素的大小变化。它可以帮助开发者在元素的宽度或高度发生改变时执行某些操作&#xff0c;比如调整布局、重新渲染内容等。 二、Resize Observer和监听resize的区别及其…

《探索Zynq MPSoC》学习笔记(三)

引言&#xff1a;本文简要介绍FPGA器件技术发展以及当今FPGA器件的体系架构和特性。 第二章 FPGA、Zynq和Zynq MPSoC&#xff08;2&#xff09; 在本章涵盖的三种器件类型中&#xff0c;FPGA是建立时间最长的&#xff0c;也是Zynq和Zynq MPSoC器件PL元件的基础。因此&#xf…

支持用户注册和登录、发布动态、点赞、评论、私信等功能的社交媒体平台创建!!!

需要整体源代码的可以在我的代码仓下载https://gitcode.com/speaking_me/social-media-platformTest.git 社交媒体平台 描述&#xff1a;社交媒体平台需要支持用户注册、发布动态、点赞、评论、私信等功能。 技术栈&#xff1a; 前端&#xff1a;React, Angular, Vue.js后端…

跨平台WPF框架Avalonia教程 十五

ListBox 列表框 列表框从元素源集合中显示多行元素&#xff0c;并允许选择单个或多个。 列表中的元素可以组合、绑定和模板化。 列表的高度会扩展以适应所有元素&#xff0c;除非特别设置&#xff08;使用高度属性&#xff09;&#xff0c;或由容器控件设置&#xff0c;例如…

STL之mapset续|红黑树篇

STL之map&set续|红黑树篇 红黑树红黑树的规则红黑树的模拟实现 map&set的模拟实现封装map/set关于红黑树的复用红黑树模板参数set的const迭代器问题 红黑树 红黑树也是一种搜索二叉树&#xff0c;它通过颜色和规则控制树上没有一条路径会比其他路径长两倍&#xff0c;…

三、计算机视觉_03LeNet5及手势识别案例

1 LeNet-5基本介绍 LeNet-5是一种经典的卷积神经网络&#xff08;CNN&#xff09;架构&#xff0c;由Yann LeCun在1998年提出&#xff0c;用于手写数字识别&#xff0c;LeNet-5是卷积神经网络的开创性工作之一&#xff0c;它引入了卷积层、池化层和全连接层的组合&#xff0c;为…

【论文模型复现】深度学习、地质流体识别、交叉学科融合?什么情况,让我们来看看

文献&#xff1a;蓝茜茜,张逸伦,康志宏.基于深度学习的复杂储层流体性质测井识别——以车排子油田某井区为例[J].科学技术与工程,2020,20(29):11923-11930. 本文目录 一、前言二、文献阅读-基于深度学习的复杂储层流体性质测井识别2.1 摘要2.2 当前研究不足2.3 本文创新2.4 论文…

Uni-APP+Vue3+鸿蒙 开发菜鸟流程

参考文档 文档中心 运行和发行 | uni-app官网 AppGallery Connect DCloud开发者中心 环境要求 Vue3jdk 17 Java Downloads | Oracle 中国 【鸿蒙开发工具内置jdk17&#xff0c;本地不使用17会报jdk版本不一致问题】 开发工具 HBuilderDevEco Studio【目前只下载这一个就…

Unity-Editor扩展Odin + 自定义EditorWindow记录

没有上下文&#xff0c;可能你不知道这是什么&#xff08;关于Odin Inspector) 在写一个 Odin 插件的完整文章&#xff0c;卡了三天&#xff0c;之后会放出 使用Unity的人之中 1/10 可能会使用Editor扩展&#xff0c;而这之中的又1/10的 人可能会用Odin这个Editor的附加扩展 -…

FIFO系列 - FIFO使用中需要注意的若干问题

FIFO使用中需要注意的若干问题 文章目录 FIFO使用中需要注意的若干问题前言场景1:包数据FIFO设计之冗余法场景2、FIFO数据传输之流控总结前言 场景1:包数据FIFO设计之冗余法 场景:类似图像、文字等码流数据是不需要重复被访问的,因此使用FIFO进行缓存(如果需要被存储,一…

计算机毕业设计 | springboot+vue大学城水电管理系统 校园学校物业水电管理(附源码+文档)

1&#xff0c;绪论 1.1 研究背景 随着计算机技术的发展以及计算机网络的逐渐普及&#xff0c;互联网成为人们查找信息的重要场所&#xff0c;二十一世纪是信息的时代&#xff0c;所以信息的管理显得特别重要。因此&#xff0c;使用计算机来管理大学城水电管理系统的相关信息成…

5-对象的访问权限

对象的访问权限知识点 对象的分类 在数据库中&#xff0c;数据库的表、索引、视图、缺省值、规则、触发器等等、都可以被称为数据库对象&#xff0c;其中对象主要分为两类 1、模式(schema)对象&#xff1a;模式对象可以理解为一个存储目录、包含视图、索引、数据类型、函数和…

药方新解:Spring Boot中药实验管理系统设计

3系统分析 3.1可行性分析 通过对本中药实验管理系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本中药实验管理系统采用SSM框架&#xff0c;JAVA作为开发语…

动态规划-完全背包问题——279.完全平方数

1.题目解析 题目来源 279.完全平方数——力扣 测试用例 2.算法原理 1.状态表示 完全背包问题通常都是使用一个二维数组来表示其状态&#xff0c;这里是 dp[i][j]&#xff1a;在[1,i]区间选择平方数&#xff0c;当此时已选择平方数的总和完全等于j时所选择的最小平方数个数 …

二叉树的层序遍历

一、题目 给定一个二叉树&#xff0c;返回该二叉树层序遍历的结果&#xff0c;&#xff08;从左到右&#xff0c;一层一层地遍历&#xff09; 例如&#xff1a; 给定的二叉树是{3,9,20,null,null,15,7}, 该二叉树层序遍历的结果是 [[3],[9,20],[15,7]] 二、解决方案 2.0 树…

模型训练过程的显存占用实测

依赖项说明 pip install nvitop pip install timm pip install peft后续的显存占用数据截图&#xff0c;均基于nvitop命令实现 1、模型显存占用说明 1.1 理论占用值 在 一文讲明白大模型显存占用&#xff08;只考虑单卡&#xff09;与大模型显存占用分析都对模型训练过程中…

后端分层解耦

引入 在上篇所举的例子中&#xff0c;我们将所有的代码均放在HelloControl方法之中&#xff0c;这样会导致代码的复用性、可读性较差&#xff0c;难以维护。因此我们需 三层架构 在之前的代码中&#xff0c;代码大体可以分为三部分&#xff1a;数据访问、数据逻辑处理、响应数…