当前位置: 首页 > news >正文

【LeetCode】剑指 Offer(5)

目录

写在前面:

题目:

题目的接口:

解题思路1:

代码:

过啦!!!

解题思路2:

代码:

过啦!!!

写在最后:


写在前面:

军训好累......

题目:剑指 Offer 11. 旋转数组的最小数字 - 力扣(Leetcode)

题目的接口:

class Solution {
public:int minArray(vector<int>& numbers) {}
};

解题思路1:

看到这个题目,我第一个想到的就是,

直接遍历数组,然后找出最小之就行,

用O(N)算法暴力解决。

代码:

class Solution {
public:int minArray(vector<int>& numbers) {//将Min初始化成一个很大的数int Min = INT_MAX;//遍历数组for(int i = 0;i<numbers.size();i++){//找出最小值Min = min(Min, numbers[i]);}return Min;}
};

过啦!!!

如果只是这样的话,那这题刷的可没什么质量, 

如果以后面试的时候,面试官问你怎么提高这个算法的效率,你该怎么办?

所以,我决定在写个二分来做这道题,将算法时间优化成O(logN)。

解题思路2:

因为这是原来是一个升序数组,

如果我们将旋转数组中的旋转的第一个值作为旋转点,

而旋转点就是这个数组的最小值,

所以我们直接找旋转点就行。

用二分的思想,设置 l、r 作为左右下标,取中间 mid 为中间下标。

如果numbers[mid] > numbers[r],旋转点一定在右边区间[ m + 1,j ]。

如果numbers[mid] < numbers[r],旋转点一定在左边区间[ l,m ]。

如果numbers[mid] = numbers[r],特殊情况就让 r--。

当 l = r 的时候,返回numbers[l]就是旋转点。

代码:

class Solution {
public:int minArray(vector<int>& numbers) {//左右下标int l = 0;int r = numbers.size() - 1;//二分while(l < r){int mid = (l + r) / 2;if(numbers[mid] > numbers[r]){l = mid + 1;}else if(numbers[mid] < numbers[r]){r = mid;}//特殊情况else{r--;}}return numbers[l];}
};

但其实这种方法也有缺陷,

他的时间复杂度还是O(N),只是优化了大部分的情况,

在遇到特殊情况的时候(也就是numbers[mid] = numbers[r]的时候就会退化成O(N)算法)

只是平均时间复杂度为O(logN)。

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

相关文章:

【LeetCode】剑指 Offer(5)

目录 写在前面&#xff1a; 题目&#xff1a; 题目的接口&#xff1a; 解题思路1&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 解题思路2&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 写在最后&#xff1a;…...

外包出来,朋友内推我去一家公司,问的实在是太...

外包出来&#xff0c;没想到算法死在另一家厂子&#xff0c;自从加入这家公司&#xff0c;每天都在加班&#xff0c;钱倒是给的不少&#xff0c;所以也就忍了。没想到8月一纸通知&#xff0c;所有人不许加班&#xff0c;薪资直降30%&#xff0c;顿时有吃不起饭的赶脚。 好在有…...

刷题记录:牛客NC54585小魂和他的数列 [线段树卡常,真恶心]

传送门:牛客 题目描述: 一天&#xff0c;小魂正和一个数列玩得不亦乐乎。 小魂的数列一共有n个元素&#xff0c;第i个数为Ai。 他发现&#xff0c;这个数列的一些子序列中的元素是严格递增的。 他想知道&#xff0c;这个数列一共有多少个长度为K的子序列是严格递增的。 请你帮…...

2019蓝桥杯真题旋转 C语言/C++

题目描述 图片旋转是对图片最简单的处理方式之一&#xff0c;在本题中&#xff0c;你需要对图片顺时针旋转 90 度。 我们用一个 nm 的二维数组来表示一个图片&#xff0c;例如下面给出一个 34 的 图片的例子&#xff1a; 1 3 5 7 9 8 7 6 3 5 9 7 这个图片顺时针旋转 90 度…...

<JVM上篇:内存与垃圾回收篇>11 - 垃圾回收相关算法

对象存活判断 在堆里存放着几乎所有的 Java 对象实例&#xff0c;在 GC 执行垃圾回收之前&#xff0c;首先需要区分出内存中哪些是存活对象&#xff0c;哪些是已经死亡的对象。只有被标记为己经死亡的对象&#xff0c;GC 才会在执行垃圾回收时&#xff0c;释放掉其所占用的内存…...

狂飙Linux平台,软件部署大全

&#x1f4e2;&#x1f4e2;&#x1f4e2;&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&am…...

积分球原理及积分球类型介绍

标题积分球标准型积分球LED积分球均匀光源便携式高亮度积分球均匀光源微光积分球均匀光源积分球均匀光源iSphere高光谱响应光学积分球其他分类积分球 积分球原理:由于球体内整涂有白色漫反射材料的空腔球体&#xff0c;球壁上开有采样口&#xff0c;当待测样品光源进入积分球的…...

Vision Transformer(ViT) 2: 应用及代码讲解

文章目录1. 代码讲解1.1 PatchEmbed类1&#xff09;__init__ 函数2) forward 过程1.2 Attention类1&#xff09;__init__ 函数2&#xff09;forward 过程1.3 MLP类1&#xff09;__init__ 函数2&#xff09;forward函数1.4 Block类1&#xff09;__init__ 函数2&#xff09;forwa…...

高频面试题|JVM虚拟机的体系结构是什么样的?

一. 前言最近有很多小伙伴都在找工作&#xff0c;他们在面试时经常被面试官问到一个问题&#xff1a;请说说JVM虚拟机的体系结构是什么样的?很多小伙伴都能说出堆、栈等相关内容&#xff0c;但面试官紧接着又问&#xff0c;你还知道其他内容吗&#xff1f;这时不少小伙伴就语塞…...

MyBatis-Plus详细讲解(整合spring Boot)

哈喽&#xff0c;大家好&#xff0c;今天带大家了解的是MyBatis-Plus&#xff08;简称 MP&#xff09;&#xff0c;是一个 MyBatis 的增强工具&#xff0c;在 MyBatis 的基础上只做增强不做改变&#xff0c;为简化开发、提高效率而生。首先说一下MyBatis-Plus的愿景是什么&…...

骨传导耳机是不是智商税?骨传导耳机真的不伤耳吗?

很多人对骨传导耳机是具有一定的了解&#xff0c;但是对骨传导耳机还是有一定的刻板印象&#xff0c;那么骨传导耳机到底是不是智商税呢&#xff1f;主要还是要从骨传导耳机传声原理上讨论。 骨传导耳机是属于固体传声的一种方式&#xff0c;通过骨骼传递声音&#xff0c;在使用…...

模拟实现string

目录 1、基本成员变量 2、默认成员函数 构造函数 析构函数 拷贝构造函数(深拷贝) 赋值运算符重载 3、容量与大小相关的函数 size capacity 4、字符串访问相关函数 operator [ ]重载 迭代器 5、增加的相关函数 reserve扩容 resize push_back追加字符 appe…...

自监督表征预训练之掩码图像建模

自监督表征预训练之掩码图像建模 前言 目前&#xff0c;在计算机视觉领域&#xff0c;自监督表征预训练有两个主流方向&#xff0c;分别是对比学习&#xff08;contrastive learning&#xff09;和掩码图像建模&#xff08;masked image modeling&#xff09;。两个方向在近几…...

华为OD机试题 - 磁盘容量(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

ChatGPT:“抢走你工作的不会是 AI ,而是先掌握 AI 能力的人”

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; ChatGPT&#xff1a;“抢走你工作的不会是 AI &#xff0c;而是先掌握 AI 能力的人” ChatGPT&#xff1a;美国OpenAI 研发的聊天机器人程序&#xff0c;人工智能技术…...

数据结构与算法(Java版) | 线性结构和非线性结构

之前&#xff0c;我们说过&#xff0c;数据结构是算法的基础&#xff0c;因此接下来在这一讲我就要来给大家重点介绍一下数据结构了。 首先&#xff0c;大家需要知道的是&#xff0c;数据结构包括两部分&#xff0c;即线性结构和非线性结构。知道这点之后&#xff0c;接下来我…...

电商数据查询平台:母婴行业妈妈用品全网热销,头部品牌格局初现

以往&#xff0c;奶粉、纸尿裤这类产品基本就代表了整体母婴市场中的消费品。而如今&#xff0c;随着母婴行业的高速发展和消费升级&#xff0c;母婴商品的种类日益丰富&#xff0c;需求也不断深入。 在京东平台&#xff0c;母婴大品类中除了包含婴童相关的食品&#xff08;奶粉…...

STM32模拟SPI协议获取24位模数转换(24bit ADC)芯片AD7791电压采样数据

STM32模拟SPI协议获取24位模数转换&#xff08;24bit ADC&#xff09;芯片AD7791电压采样数据 STM32大部分芯片只有12位的ADC采样性能&#xff0c;如果要实现更高精度的模数转换如24位ADC采样&#xff0c;则需要连接外部ADC实现。AD7791是亚德诺(ADI)半导体一款用于低功耗、24…...

华为OD机试题 - 交换字符(JavaScript)| 代码+思路+重要知识点

最近更新的博客 华为OD机试题 - 字符串加密(JavaScript) 华为OD机试题 - 字母消消乐(JavaScript) 华为OD机试题 - 字母计数(JavaScript) 华为OD机试题 - 整数分解(JavaScript) 华为OD机试题 - 单词反转(JavaScript) 使用说明 参加华为od机试,一定要注意不要完全背…...

最好的工程师像投资者一样思考,而不是建设者

我在大学期间住在图书馆。“我学习的教科书理论越多&#xff0c;我就会成为一名更好的工程师&#xff0c;”我想。然而&#xff0c;当我开始工作时&#xff0c;我注意到业内最优秀的工程师并不一定比应届毕业生了解更多的理论。他们只是带来了不同的心态&#xff0c;即投资者的…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

代码随想录刷题day30

1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币&#xff0c;另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额&#xff0c;返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...