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

【刷题之路Ⅱ】牛客 NC107 寻找峰值

【刷题之路Ⅱ】牛客 NC107 寻找峰值

  • 一、题目描述
  • 二、解题
    • 1、方法1——直接遍历
      • 1.1、思路分析
      • 1.2、代码实现
    • 2、方法2——投机取巧的求最大值
      • 2.1、思路分析
      • 2.2、代码实现
    • 3、方法3——二分法
      • 3.1、思路分析
      • 3.2、代码实现

一、题目描述

原题连接: NC107 寻找峰值

题目描述:
给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] =−∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗?
数据范围:1≤nums.length≤2×10^5
-231<=nums[i]<=231 −1

示例1
输入:[2,4,1,2,7,8,4]
返回值: 1
说明:4和8都是峰值元素,返回4的索引1或者8的索引5都可以

示例2
输入:[1,2,3,1]
返回值: 2
说明:3 是峰值元素,返回其索引 2

二、解题

1、方法1——直接遍历

1.1、思路分析

我们可以直接遍历数组,但有两个情况需要特殊考虑。
当i等于0时,判断nums[i]是否大于nums[i + 1],若大于,则返回i;
当i等于numsLen - 1时,判断nums[i]是否大于nums[i - 1],若大于,则返回i;
其他情况判断是否有nums[i] > nums[i - 1] && nums[i] > nums[i + 1],如果成立,则返回i。

1.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int findPeakElement1(int* nums, int numsLen) {assert(nums);if (1 == numsLen) {return 0;}int i = 0;for (i = 0; i < numsLen; i++) {if (0 == i) {if (nums[i] > nums[i + 1]) {return i;}}else if (numsLen - 1 == i) {if (nums[i] > nums[i - 1]) {return i;}}else if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {return i;}}return -1;
}

时间复杂度:O(n),n为数组元素个数。
空间复杂度:O(1),我们只需要用到常数级的额外空间

2、方法2——投机取巧的求最大值

2.1、思路分析

根据题目的描述:“对于所有有效的 i 都有 nums[i] != nums[i + 1]”,且返回任意一个就行。
就有一个非常投机取巧的方法就是直接找到数组中的最大值,返回其下标就行了。
这个方法之所有有效是因为峰值不一定是最大值,但最大值一定是峰值。😏
在这里插入图片描述

2.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int findPeakElement2(int* nums, int numsLen) {assert(nums);if (1 == numsLen) {return 0;}int max = nums[0];int index = 0;int i = 0;for (i = 1; i < numsLen; i++) {if (nums[i] > max) {max = nums[i];index = i;}}return index;
}

时间复杂度:O(n),n为数组元素个数,我们只需要遍历一遍数组即可。
空间复杂度:O(1),我们只需要用到常数级的额外空间。

3、方法3——二分法

3.1、思路分析

我们其实可以使用二分法来是我们的left和right每一次都向"峰值"靠近。
当left和right重合时即找到了峰值。
具体做法如下:
1、当nums[mid] < nums[mid + 1]时,说明从下标mid到下标mid + 1是在走上坡路:
在这里插入图片描述
则可以肯定此时的mid一定不是峰值,所以执行left = mid + 1,使区间向峰值靠近。
在这里插入图片描述
2、当nums[mid] > nums[mid + 1]时,说明从下标mid到下标mid + 1是在走下坡路:
在这里插入图片描述
则mid可能是峰值,此时应该执行right = mid(不能跳过mid,因为mid可能是峰值),使区间向峰值靠近。
在这里插入图片描述
最后当left和right重合时,说明我们已经找到了峰值。

3.2、代码实现

有了以上思路,那我们写起代码来也就水到渠成了:

int findPeakElement3(int* nums, int numsLen) {assert(nums);int left = 0;int right = numsLen - 1;int mid = 0;while (left < right) {mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1]) {left = mid + 1;}else {right = mid;}}return left;
}

时间复杂度:O(log2N),其中N为数组元素个数,最坏情况下,我们要对整个数组进行二分,所以时间复杂度为O(log2N)。
空间复杂度:O(1),我们只需要用到常数级的额外空间。

相关文章:

【刷题之路Ⅱ】牛客 NC107 寻找峰值

【刷题之路Ⅱ】牛客 NC107 寻找峰值一、题目描述二、解题1、方法1——直接遍历1.1、思路分析1.2、代码实现2、方法2——投机取巧的求最大值2.1、思路分析2.2、代码实现3、方法3——二分法3.1、思路分析3.2、代码实现一、题目描述 原题连接&#xff1a; NC107 寻找峰值 题目描…...

智能灯泡一Homekit智能家居系列

传统的灯泡是通过手动打开和关闭开关来工作。有时&#xff0c;它们可以通过声控、触控、红外等方式进行控制&#xff0c;或者带有调光开关&#xff0c;让用户调暗或调亮灯光。 智能灯泡内置有芯片和通信模块&#xff0c;可与手机、家庭智能助手、或其他智能硬件进行通信&#…...

外包离职,历时学习416天,成功上岸百度,分享成长过程~

前言&#xff1a; 没有绝对的天才&#xff0c;只有持续不断的付出。对于我们每一个平凡人来说&#xff0c;改变命运只能依靠努力幸运&#xff0c;但如果你不够幸运&#xff0c;那就只能拉高努力的占比。 2020年7月&#xff0c;我有幸成为了百度的一名Java后端开发&#xff0c…...

利用客户支持建立忠诚度和竞争优势

客户支持可以极大地改变您的业务;最细微、最微妙的差异都会使拥有一次性客户和拥有终身客户之间产生差异。在这篇博文中&#xff0c;我们将揭示客户对企业的忠诚度的三种核心类型&#xff0c;以及如何利用强大的客户支持工具和原则来提高理想的忠诚度并获得决定性的竞争优势。一…...

看他人代码小总结

针对几个功能类似的函数&#xff1a; 1.需要经常调试则定义一个参数比如is_debug来选择是否在调试&#xff0c;定义一些参数专门用于调试用&#xff0c;不用每次都修改这些参数&#xff0c;只需要修改is_debug这个参数&#xff1b; 2.把其中的变量(常量)单独拎出来放到一个文件…...

cudaMemGetInfo()函数cudaDeviceGetAttribute()函数来检查设备上的可用内存

使用CUDA Runtime API中的cudaMemGetInfo()函数来检查设备上的可用内存。该函数将返回当前可用于分配的总设备内存大小和当前可用于分配的最大单个内存块大小。 示例代码&#xff0c;演示了如何在分配内存之前和之后调用cudaMemGetInfo()函数来检查可用内存 size_t free_byte…...

【基础阶段】01中华人民共和国网络安全法

文章目录1 网络安全行业介绍2 什么是黑客和白帽子3 网络安全课程整体介绍4 网络安全的分类5 常见的网站攻击方式6 安全常见术语介绍7 《网络安全法》制定背景和核心内容8 《全国人大常委会关于维护互联网安全的决定》9《中华人民共和国计算机信息系统安全保护条例》10 《中华人…...

隐私计算领域大咖推荐,这些国内外导师值得关注

开放隐私计算 经过近一个月的信息收集&#xff0c;研习社已经整理了多位国内外研究隐私计算的导师资料。邻近考研复试&#xff0c;研习社希望小伙伴们能够通过本文整理的信息&#xff0c;选择自己心仪的老师&#xff0c;在研究生的路途上一帆风顺&#xff01;1. 国内隐私计算导…...

009 uni-app之vue、vuex

vue.js 视频教程 vue3.js 中文官网 vue.js 视频教程 vue语法&#xff1a;https://uniapp.dcloud.net.cn/tutorial/vue-vuex.html vue2迁移到 vue3&#xff1a;https://uniapp.dcloud.net.cn/tutorial/migration-to-vue3.html Vuex Vuex 是一个专为 Vue.js 应用程序开发的…...

Linux防火墙——SNAT、DNAT

目录 NAT 一、SNAT策略及作用 1、概述 SNAT应用环境 SNAT原理 SNAT转换前提条件 1、临时打开 2、永久打开 3、SNAT转换1&#xff1a;固定的公网IP地址 4、SNAT转换2&#xff1a;非固定的公网IP地址&#xff08;共享动态IP地址&#xff09; 二、SNAT实验 配置web服务…...

递归理解三:深度、广度优先搜索,n叉树遍历,n并列递归理解与转非递归

参考资料&#xff1a; DFS 参考文章BFS 参考文章DFS 参考视频二叉树遍历规律递归原理源码N叉树规律总结&#xff1a; 由前面二叉树的遍历规律和递归的基本原理&#xff0c;我们可以看到&#xff0c;二叉树遍历口诀和二叉树递推公式有着紧密的联系 前序遍历&#xff1a;F(x…...

MATLAB 2023a安装包下载及安装教程

[软件名称]:MATLAB 2023a [软件大小]: 12.2 GB [安装环境]: Win11/Win 10/Win 7 [软件安装包下载]:https://pan.quark.cn/s/8e24d77ab005 MATLAB和Mathematica、Maple并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。行矩阵运算、绘制函数和数据、实现算…...

QT学习开发笔记(数据库之实用时钟)

数据库 数据库是什么&#xff1f;简易言之&#xff0c;就是保存数据的文件。可以存储大量数据&#xff0c;包括插入数据、更 新数据、截取数据等。用专业术语来说&#xff0c;数据库是“按照数据结构来组织、存储和管理数据的 仓库”。是一个长期存储在计算机内的、有组织的、…...

Docker常规安装简介

总体步骤 搜索镜像拉取镜像查看镜像启动镜像,服务端口映射停止容器移除容器 案例 安装tomcat docker hub上面查找tomcat镜像&#xff0c;docker search tomcat从docker hub上拉取tomcat镜像到本地 docker pull tomcatdocker images查看是否有拉取到的tomcat 使用tomcat镜像创…...

Python - PyQT5 - ui文件转为py文件

在QTdesigner图形化编辑工具中&#xff0c;有些控件我们是可以直接在编辑界面进行编辑的&#xff0c;有些是不可以编辑的&#xff0c;只能通过Python代码进行编辑&#xff0c;不过总体来说&#xff0c;所有能够通过图形化编辑界面可以编辑的&#xff0c;都可以通过Python语言实…...

分布式事务和分布式锁

1、关于分布式锁的了解&#xff1f; 原理&#xff1a;控制分布式系统有序的去对共享资源进行操作&#xff0c;通过互斥来保持一致性。 具备的条件&#xff1a; ①分布式环境下&#xff0c;一个方法在同一时间只能被一个机器的一个线程执行 ②高可用的获取锁和释放锁 ③高性能…...

JAVA-4-[Spring框架]基于XML方式的Bean管理

1 Spring IOC容器 (1)IOC底层原理 (2)IOC接口(BeanFactory) (3)IOC操作Bean管理(基于XML) (4)IOC操作Bean管理(基于注释) 1.1 IOC概念 (1)控制反转(Inversion of Control)&#xff0c;把对象的创建和对象之间的调用过程&#xff0c;交给Spring进行管理。 (2)使用IOC目的&…...

路科验证UVM入门与进阶详解实验0

一.代码编译 首先创建新项目&#xff0c;导入lab0 的UVM文件&#xff1b; 针对uvm_compile文件&#xff0c;先进行编译&#xff1b; module uvm_compile;// NOTE:: it is necessary to import uvm package and macrosimport uvm_pkg::*;include "uvm_macros.svh"in…...

Linux之Shell编程(1)

文章目录前言一、Shell是什么二、Shell脚本的执行方式脚本的常用执行方式三、Shell的变量Shell变量介绍shell变量的定义四、设置环境变量基本语法快速入门五、位置参数变量介绍●基本语法●位置参数变量六、预定义变量基本介绍基本语法七、运算符基本介绍基本语法前言 为什么要…...

Java问题诊断工具——JVisualVM

这篇文章源自一次加班改bug的惨痛经历[,,_,,]:3负责的一个项目占用不断增加&#xff0c;差点搞崩服务器(╥﹏╥)……一下子有点懵&#xff0c;不能立刻确定是哪里导致的问题&#xff0c;所以决定好好研究下这个之前一直被我忽视的问题诊断工具&#x1f527;——JVisualVM嘿嘿我…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

FFmpeg:Windows系统小白安装及其使用

一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】&#xff0c;注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录&#xff08;即exe所在文件夹&#xff09;加入系统变量…...