【LeetCode】33. 搜索旋转排序数组

1 问题

整数数组 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

2 答案

自己写的,不知道时间复杂度是不是 O(log n) ,好像不符合要求

class Solution:def search(self, nums: List[int], target: int) -> int:if nums[0] == target:return 0elif nums[0] < target:for i in range(len(nums)):if nums[i] == target:return ielse:for i in range(len(nums)-1,0,-1):if nums[i] == target:return ireturn -1

在这里插入图片描述
官方解,使用二分法,边界确定比较困难

class Solution:def search(self, nums: List[int], target: int) -> int:left = 0right = len(nums) - 1while left < right:mid = (right - left) // 2 + left  # mid属于左边的序列if nums[mid] == target:return mid# 左边是有序的if nums[mid] > nums[left]:if nums[left] <= target <= nums[mid]:right = midelse:# 这里 +1,因为上面是 <= 符号left = mid + 1# 右边是有序的else:# 注意:这里必须是 mid+1,因为根据我们的比较方式,mid属于左边的序列if nums[mid+1] <= target <= nums[right]:left = mid + 1else:right = midreturn left if nums[left] == target else -1

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】Ubuntu美化bash【教程】

【Linux】Ubuntu美化bash【教程】 文章目录 【Linux】Ubuntu美化bash【教程】1. 查看当前环境中是否有bash2. 安装Synth-Shell3. 配置Synth-Shell4. 取消greeterReference 1. 查看当前环境中是否有bash 查看当前使用的bash echo $SHELL如下所示 sjhsjhR9000X:~$ echo $SHELL…

在 Android 上恢复已删除音乐的 5 种简单方法

人们经常将重要的音乐文件保存在智能手机上&#xff0c;以方便随时随地收听自己喜欢的曲目。但是&#xff0c;如果这些珍贵的音乐文件因软件故障或硬件故障而被意外删除或丢失怎么办&#xff1f;这将是许多音乐爱好者的噩梦&#xff01; 如果您也是这些人中的一员&#xff0c;…

Linux shell编程学习笔记13:文件测试运算

Linux Shell 脚本编程和其他编程语言一样&#xff0c;支持算数、关系、布尔、逻辑、字符串、文件测试等多种运算。前面几节我们依次研究了 Linux shell编程 中的 字符串运算、算术运算、关系运算、布尔运算 和 逻辑运算&#xff0c;今天我们来研究 Linux shell编程中的文件测…

【设计模式-1】UML和设计原则

说明&#xff1a;设计模式&#xff08;Design Pattern&#xff09;对于软件开发&#xff0c;简单来说&#xff0c;就是软件开发的套路&#xff0c;固定模板。在学习设计模式之前&#xff0c;需要首先学习UML&#xff08;Unified Modeling Language&#xff0c;统一建模语言&…

(Python) Python中三种时间格式的转换方法

1. 时间元组 1.1. 时间元组和时间戳的互相转化 import time,datetime # 获取当前时间的时间元组 t time.localtime() print(t) # 时间元组转时间戳 timestamp time.mktime(t) print(timestamp) # time.struct_time(tm_year2019, tm_mon10, tm_mday23, tm_hour23, tm_min15,…

漏洞复现--安恒明御安全网关文件上传

免责声明&#xff1a; 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直…

web 安全总结

1、web安全总结 1.1 web安全简介 1.1.1 http协议 http 协议是超文本传输协议-明文传输 https 协议是http协议的基础上进行升级&#xff0c;是数据在传输过程中进行加密 1.1.2 http请求 http请求分为&#xff1a;请求方法、请求头、请求体 GET、PUT、POST、OPTIONS、move、…

【Unity HDRP渲染管线下的WorleyUtilities文件,“Hash”函数】

Unity HDRP内置文件WorleyUtilities WorleyUtilities文件路径如下:文件代码如下然后转译到ShaderLab中:存档:WorleyUtilities文件路径如下: D:…\Library\PackageCache\com.unity.render-pipelines.high-definition@14.0.8\Runtime\Lighting\VolumetricClouds\WorleyUtili…

Ubuntu - 查看 IP 地址

要查看 Ubuntu 操作系统中的 IP 地址&#xff0c;可以使用 ip 命令或者 ifconfig 命令。以下是使用这两个命令的示例&#xff1a; 使用 ip 命令&#xff1a; 打开终端。 输入以下命令&#xff1a; ip a 这将显示网络接口信息&#xff0c;包括 IP 地址。通常&#xff0c;IP…

安科瑞预付费电能管理系统在学生公寓的应用与分析

安科瑞 崔丽洁 摘要&#xff1a;论文设计了适用于学生公寓的自助式预付费控电控水管理系统&#xff0c;采用多种智能功能&#xff0c;可以监测和显示漏电现象&#xff0c;通过短路、跳线、零线接地等方式防范和记录用户的偷电行为&#xff0c;通过报警和拉闸防止事故的发生。预…

嵌入式实时操作系统的设计与开发(调度策略学习)

将调度分为两层&#xff0c;上层为策略&#xff0c;下层为机制&#xff0c;并且采用策略与机制分离的设计原则&#xff0c;可以方便灵活地扩展调度策略&#xff0c;而不改变底层的调度机制。 调度策略就是如何确定线程的CPU、优先级prio等参数&#xff0c;线程是按照FIFO&…

掌控安全Update.jsp SQL注入

0x01 漏洞介绍 亿赛通电子文档安全管理系统是国内最早基于文件过滤驱动技术的文档加解密产品之一&#xff0c;保护范围涵盖终端电脑&#xff08;Windows、Mac、Linux系统平台&#xff09;、智能终端&#xff08;Android、IOS&#xff09;及各类应用系统&#xff08;OA、知识管理…

metaRTC7集成lvgl ui demo编译指南

概要 开源轻量级嵌入式图形库lvgl:Light and Versatile Graphics Library&#xff0c;最低只需8kb内存&#xff0c;可为任何 MCU、MPU 和显示类型创建漂亮的 UI。 metaRTC新增lvgl demo&#xff0c;可在linux下编译运行。 源码下载 https://github.com/metartc/metaRTC/rel…

小程序首页搭建

小程序首页搭建 1. Flex布局是什么&#xff1f;2. 容器的属性2.1 flex-direction属性2.2 flex-wrap属性2.3 flex-flow属性2.4 justify-content属性2.5 align-items属性2.6 align-content属性 二.首页布局搭建二.1moke模拟数据实现轮播图4.信息搭建 Flex弹性布局 1. Flex布局是…

Docker基础操作命令演示

Docker中的常见命令&#xff0c;可以参考官方文档&#xff1a;https://docs.docker.com/engine/reference/commandline/cli/ 1、常见命令介绍 其中&#xff0c;比较常见的命令有&#xff1a; 命令说明文档地址docker pull拉取镜像docker pulldocker push推送镜像到DockerReg…

【塔防】1,游戏架构

游戏架构 一&#xff0c;StoneDefence核心架构分析1&#xff0c;安装2&#xff0c;核心框架2.1创建核心核心环境2.1.1游戏中的核心元素&#xff08;GameCore&#xff09;ApawnGameInstanceGameStatePlayerStatePlayerControllerGameUserSettings 2.1.2大厅中的核心元素&#xf…

水库大坝安全监测是什么和主要作用?

水库大坝安全监测是指通过仪器观测和巡视检查对水利水电工程主体结构、地基基础、两岸边坡、相关设施以及周围环境所作的测量及观察。大坝安全监测是作为水库大坝安全管理的重要组成部分&#xff0c;是掌握水库大坝安全性态的重要手段&#xff0c;是科学调度、安全运行的前提。…

BI零售数据分析,当代零售企业的核心竞争力

在数字化转型中&#xff0c;BI智能零售数据分析成为了极其重要的核心竞争力之一。通过对大数据的采集和分析&#xff0c;零售企业可以更好地了解消费者的需求和行为模式&#xff0c;从而做出更准确的决策。例如&#xff0c;通过分析消费者的购物历史、浏览记录等数据&#xff0…

【微信小程序】6天精准入门(第1天:小程序入门)

一、介绍 1、什么是小程序 小程序是一种轻量级的应用程序&#xff0c;可以在移动设备上运行&#xff0c;不需要用户下载和安装。它们通常由企业或开发者开发&#xff0c;用于提供特定功能或服务。 微信小程序&#xff08;wei xin xiao cheng xu&#xff09;&#xff0c;简称小程…

Linux centos安装SQL Server数据库,结合cpolar内网穿透实现公网访问

文章目录 前言1. 安装sql server2. 局域网测试连接3. 安装cpolar内网穿透4. 将sqlserver映射到公网5. 公网远程连接6.固定连接公网地址7.使用固定公网地址连接 前言 简单几步实现在Linux centos环境下安装部署sql server数据库&#xff0c;并结合cpolar内网穿透工具&#xff0…