(二分查找) 11. 旋转数组的最小数字 ——【Leetcode每日一题】
❓剑指 Offer 11. 旋转数组的最小数字
难度:简单
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转,该数组的最小值为 1。
注意,数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
示例 1:
输入:numbers = [3,4,5,1,2]
输出:1
示例 2:
输入:numbers = [2,2,2,0,1]
输出:0
提示:
n == numbers.length1 <= n <= 5000-5000 <= numbers[i] <= 5000numbers原来是一个升序排序的数组,并进行了1至n次旋转
注意:本题与 154. 寻找旋转排序数组中的最小值 II 相同。
💡思路:二分查找
将旋转数组对半分可以得到一个包含最小元素的新旋转数组,以及一个非递减排序的数组。新的旋转数组的长度是原数组的一半,从而将问题规模减少了一半,这种折半性质的算法的时间复杂度为 O ( l o g 2 N ) O(log2N) O(log2N)。

此时问题的关键在于确定对半分得到的两个数组哪一个是旋转数组,哪一个是非递减数组。我们很容易知道非递减数组的第一个元素一定小于等于最后一个元素。
通过修改二分查找算法进行求解(left、mid、right 分别代表包含最小元素的新旋转数组 左、中、右):
- 当
numbers[mid] > numbers[right]时,[left,mid]区间内的数组是非递减数组,[mid + 1, right]区间内的数组为新的旋转数组,此时,left = mid + 1; - 当
numbers[mid] < numbers[right]时,[mid,right]区间内的数组是非递减数组,[left, mid]区间内的数组为新的旋转数组,此时,right = mid; - 当
numbers[mid] = numbers[right]时, 无法判断哪一个是旋转数组,哪一个是非递减数组,此时right- -,直到能判断。
🍁代码:(C++、Java)
C++
class Solution {
public:int minArray(vector<int>& numbers) {int left = 0;int right = numbers.size() - 1;if(right == 0) return numbers[0];while(left < right){int mid = left + (right - left) / 2;if(numbers[mid] > numbers[right]){left = mid + 1;}else if(numbers[mid] < numbers[right]){right = mid;}else{right--;}}return numbers[left];}
};
Java
class Solution {public int minArray(int[] numbers) {int left = 0;int right = numbers.length - 1;if(right == 0) return numbers[0];while(left < right){int mid = left + (right - left) / 2;if(numbers[mid] > numbers[right]){left = mid + 1;}else if(numbers[mid] < numbers[right]){right = mid;}else{right--;}}return numbers[left];}
}
🚀 运行结果:

🕔 复杂度分析:
- 时间复杂度: O ( l o g n ) O(logn) O(logn),平均时间复杂度为 O ( l o g n ) O(logn) O(logn),其中
n是数组numbers的长度。如果数组是随机生成的,那么数组中包含相同元素的概率很低,在二分查找的过程中,大部分情况都会忽略一半的区间。而在最坏情况下,如果数组中的元素完全相同,那么while循环就需要执行n次,每次忽略区间的右端点,时间复杂度为O(n)。 - 空间复杂度: O ( 1 ) O(1) O(1)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
(二分查找) 11. 旋转数组的最小数字 ——【Leetcode每日一题】
❓剑指 Offer 11. 旋转数组的最小数字 难度:简单 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 给你一个可能存在 重复 元素值的数组 numbers ,它原来是一个升序排列的数组,并按上述情形进行了一次旋转…...
docker 制作tomcat镜像
需要下载tomcat安装包和jdk安装包,我这边下载的jdk版本分别为(jdk和tomcat版本需要对应上) apache-tomcat-9.0.78.tar.gzjdk-8u381-linux-x64.tar.gz创建一个readme.txt空文件 readme.txt创建一个Dockerfile文件 # centos系统作为底层 FROM …...
年之年的选择,组装版
组件:<!--* Author: liuyu liuyuxizhengtech.com* Date: 2023-02-01 16:57:27* LastEditors: wangping wangpingxizhengtech.com* LastEditTime: 2023-06-30 17:25:14* Description: 时间选择年 - 年 --> <template><div class"year-range-pick…...
英语词法——代词
代词是用来代替名词、起名词作用的短语、分句和句子的词。英语中代词根据其意义和作用可分为九类:人称代词、物主代词、反身代词、相互代词、指示代词、疑问代词、不定代词、关系代词和连接代词。 第一节 人称代词 一、人称代词的形式和用法 人称代词单数复数第一人称第二人…...
1475.商品折扣后的最终价格
文章目录 题目描述解题思路:方法一:通俗解法方法二:单调栈 leetcode原题链接 1475. 商品折扣后的最终价格 题目描述 给你一个数组 prices ,其中 prices[i] 是商店里第 i 件商品的价格。 商店里正在进行促销活动,如果你…...
php、 go 语言怎么结合构建高性能高并发商城。
一、php、 go 语言怎么结合构建高性能高并发商城。 将PHP和Go语言结合起来构建高性能高并发的商城系统可以通过多种方法实现,以利用两种语言的优势。下面是一些可能的方法和策略: 1. **微服务架构:** 使用微服务架构,将系统拆分…...
ubuntu 部署 ChatGLM-6B 完整流程 模型量化 Nvidia
ubuntu 部署 ChatGLM-6B 完整流程 模型量化 Nvidia 初环境与设备环境准备克隆模型代码部署 ChatGLM-6B完整代码 ChatGLM-6B 是一个开源的、支持中英双语的对话语言模型,基于 General Language Model (GLM) 架构,具有 62 亿参数。结合模型量化技术&#x…...
【数据分享】2001-2022年我国省市县镇四级的逐月最高气温数据(无需转发/Shp/Excel格式)
气象数据是在各项研究中都非常常用的数据!之前我们分享过来自于国家青藏高原科学数据中心的1901-2022年1km分辨率的逐月平均气温栅格数据,以及基于该栅格数据处理的Shp和Excel格式的2001-2022年我国省市县镇四级的逐月平均气温数据(可查看之前…...
线段树-模板-区间查询-区间修改
【模板】线段树 2 传送门:https://www.luogu.com.cn/problem/P3373 题单:https://www.luogu.com.cn/training/16376#problems 题目描述 如题,已知一个数列,你需要进行下面三种操作: 将某区间每一个数乘上 x x x&a…...
微服务架构和分布式架构的区别
微服务架构和分布式架构的区别 有:1、含义不同;2、概念层面不同;3、解决问题不同;4、部署方式不同;5、耦合度不同。其中,含义不同指微服务架构是一种将一个单一应用程序开发为一组小型服务的方法ÿ…...
Ajax-概念、Http协议、Ajax请求及其常见问题
Ajax Ajax概念Ajax优缺点HTTP协议请求报文响应报文 Ajax案例准备工作express基本使用创建一个服务器 发送AJAX请求GET请求POST请求JSON响应 Ajax请求出现的问题IE缓存问题Ajax请求超时与网络异常处理Ajax手动取消请求Ajax重复发送请求问题 Ajax概念 AJAX 全称为Asynchronous J…...
react 09之状态管理工具1 redux+ react-thunk的使用实现跨组件状态管理与异步操作
目录 react 09之状态管理工具1 redux react-thunk的使用实现跨组件状态管理与异步操作store / index.js store的入口文件index.js 在项目入口文件 引入store / actionType.js 定义action的唯一标识store / reducers / index.jsstore / actions / form.jsstore / reducers / for…...
opencv实战项目 手势识别-实现尺寸缩放效果
手势识别系列文章目录 手势识别是一种人机交互技术,通过识别人的手势动作,从而实现对计算机、智能手机、智能电视等设备的操作和控制。 1. opencv实现手部追踪(定位手部关键点) 2.opencv实战项目 实现手势跟踪并返回位置信息&…...
Netty对HPACK头部压缩的支持
前言 HTTP2终于支持对头部进行压缩传输了,Netty很早就支持HTTP2了,看下Netty对HPACK的实现源码,可以对HPACK理解的更深一下。 HpackDecoder Netty内置的编解码器Http2FrameCodec专门用来对HTTP2的各种Frame进行编解码,其中就包…...
C++:替换string中的字符
1.按照位置进行替换 string的成员函数replace可以满足这种需求,其变体有很多种,请参考官方文档,以下列举常用的两种: #include <iostream> #include <string> using namespace std;int main() {string s = "hello world";s.replace(s.begin(), s.b…...
【ChatGPT】自我救赎
ChatGPT辅助学习C之【在C中如果大数据类型转小数据类型会发生什么呢?】,今天问ChatGPT一个问题,让它解析下面这个C程序: #include <iostream> #include <cstdio> using namespace std; int main() {int a;long long b532165478…...
微信小程序(由浅到深)
文章目录 一. 项目基本配置1. 项目组成2. 常见的配置文件解析3. app.json全局的五大配置4.单个页面中的page配置5. App函数6.tabBar配置 二. 基本语法,事件,单位1. 语法2. 事件3. 单位 三. 数据响应式修改四 . 内置组件1. button2. image3. input4. 组件…...
冒泡排序 简单选择排序 插入排序 快速排序
bubblesort 两个for循环,从最右端开始一个一个逐渐有序 #include <stdio.h> #include <string.h> #include <stdlib.h>void bubble(int *arr, int len); int main(int argc, char *argv[]) {int arr[] {1, 2, 3, 4, 5, 6, 7};int len sizeof(…...
linux文件I/O之 open() 函数用法
#include <sys/types.h> #include <sys/stat.h> #include <fcntl.h> typedef unsigned int mode_t ; int open(const char *pathname, int flags); int open(const char *pathname, int flags, mode_t mode); 函数功能 打开或创建一个文件 返回值 成功…...
用Java操作MySQL数据库
新建Maven项目 创建Maven项目 添加依赖 在pom.xml的标签里加上下面的内容 如果是MySQL 5.8那么的版本号是5.x.x, 例如5.1.49 如果是MySQL 8.0那么的版本号是8.x.x, 例如 8.0.28 <dependencies><!-- https://mvnrepository.com/artifact/mysql/mysql-connector-java …...
PHP安全漏洞之文件包含与SSRF攻击全解析
在Web安全领域,PHP应用程序的安全问题一直备受关注。本文将深入探讨两种常见的PHP安全漏洞:文件包含漏洞和服务器端请求伪造(SSRF),帮助开发者理解漏洞原理、利用方式以及防御措施。 第一部分:文件包含漏洞详解 什么是文件包含漏洞…...
春行歌(原创诗)
江河湖海卷浪涛,日月星辰北斗昊。山峰高耸明月颂,潺潺流水育万物。大道之行在至简,路途迢迢智行远。仰天长啸动九州,敢叫大千换新颜。混沌未凿辟天地,宇宙万象守天道。万法归一倡本源,百川万里寻道宗。...
跨平台BongoCat桌面宠物开发实战:从零构建互动猫咪应用
跨平台BongoCat桌面宠物开发实战:从零构建互动猫咪应用 【免费下载链接】BongoCat 🐱 跨平台互动桌宠 BongoCat,为桌面增添乐趣! 项目地址: https://gitcode.com/gh_mirrors/bong/BongoCat BongoCat是一款基于Tauri框架的跨…...
2025届毕业生推荐的六大AI辅助写作平台实际效果
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 作为人工智能技术重要应用的AI写作工具,正逐渐改变内容创作模式,此类…...
Z-Image-Turbo镜像快速入门:预置模型,一键部署文生图环境
Z-Image-Turbo镜像快速入门:预置模型,一键部署文生图环境 1. 为什么选择Z-Image-Turbo镜像 如果你正在寻找一个开箱即用的文生图解决方案,Z-Image-Turbo镜像绝对是你的理想选择。这个镜像最大的优势在于它已经预置了完整的32.88GB模型权重文…...
Qwen3-14B-Int4-AWQ在人工智能教学中的应用:交互式机器学习概念解释器
Qwen3-14B-Int4-AWQ在人工智能教学中的应用:交互式机器学习概念解释器 1. 让AI教学变得生动有趣 想象一下,当你第一次听到"卷积神经网络"这个词时是什么感觉?对大多数学生来说,这些专业术语就像一堵高墙,把…...
如何用Calibre-Douban插件解决豆瓣API关闭后的电子书元数据管理难题
如何用Calibre-Douban插件解决豆瓣API关闭后的电子书元数据管理难题 【免费下载链接】calibre-douban Calibre new douban metadata source plugin. Douban no longer provides book APIs to the public, so it can only use web crawling to obtain data. This is a calibre D…...
STM32F103C8T6实战:I2C驱动STP23L测距传感器与OLED显示优化
1. 项目背景与硬件选型 第一次接触STM32F103C8T6驱动STP23L测距传感器时,我完全没料到这个蓝色小模块会成为后续多个项目的核心组件。STP23L是一款基于TOF(飞行时间)原理的激光测距传感器,测量范围0.1-3米,精度可达1m…...
深入浅出:图解5G NR中UCI复用与资源抢占的那些事儿
5G NR上行控制信道的资源博弈:UCI复用机制全景解析 想象一下,在一个繁忙的十字路口,各种车辆(出租车、救护车、私家车)都在争夺有限的通行权。5G上行控制信道中的UCI复用场景与之惊人地相似——SR(调度请求…...
Graphormer分子预测精度解析:OGB榜单指标解读与科研论文复现指南
Graphormer分子预测精度解析:OGB榜单指标解读与科研论文复现指南 1. 引言:Graphormer模型概述 Graphormer是一种基于纯Transformer架构的图神经网络,专门为分子图(原子-键结构)的全局结构建模与属性预测而设计。与传…...
