Java旋转数组中的最小数字(图文详解版)
目录
1.题目描述
2.题解
分析
具体实现
方法一(遍历):
方法二(排序):
方法三(二分查找):
1.题目描述
有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。
示例
输入:[3, 4, 5, 1, 2]
返回值:1
2.题解
分析
题目中的数组为

题目要求我们找出其中的最小值
具体实现
方法一(遍历):
寻找数组中的最小值,遍历数组即可找到最小值
public class Solution {public int minNumberInRotateArray(int[] nums) {if(nums.length == 0){return -1;}int min = nums[0];for (int i = 1; i < nums.length; i++) {if (min > nums[i]) {min = nums[i];}}return min;}
}
方法二(排序):
使用Arrays.sort方法对数组进行降序排序,则nums[0]即为数组的最小值
import java.util.Arrays;public class Solution {public int minNumberInRotateArray (int[] nums) {if(nums.length == 0){return -1;}Arrays.sort(nums);return nums[0];}
}
方法三(二分查找):
数组原本是一个升序数组,旋转之后,数组被分成两部分,前、后半部分分别为升序,后半部分小于前半部分,我们可以利用二分查找的思想,找到其旋转点,即可找到数组的最小值
首先找到数组首尾两端元素,并求出数组中间的下标

再将数组中间值与数组首尾两端元素进行比较,
若nums[mid] > nums[right],则left = mid + 1
若nums[mid] < nums[right],则right = mid

若nums[mid] = nums[right], 则将right向左移动一位,即right--

然后进入下一次循环,循环的条件为left < right
通过不断缩小范围,最终能够找到数组的最小值

完整代码
public class Solution {public int minNumberInRotateArray(int[] nums) {if(nums.length == 0){return -1;}int left = 0;int right = nums.length - 1;while(left < right){//找到数组的中点int mid = (left + right) / 2;if(nums[mid] > nums[right]){//旋转点在[mid+1, j]中,跳过mid+1左边元素left = mid + 1;} else if(nums[mid] < nums[right]){//旋转点在[left, mid]中,跳过mid右边元素right = mid;}else{//缩小right继续查找right--;}}//返回旋转点return nums[left];}
}
注:题目出自牛客网,链接如下
旋转数组的最小数字_牛客题霸_牛客网 (nowcoder.com)
相关文章:
Java旋转数组中的最小数字(图文详解版)
目录 1.题目描述 2.题解 分析 具体实现 方法一(遍历): 方法二(排序): 方法三(二分查找): 1.题目描述 有一个长度为 n 的非降序数组,比如[1,2,3,4,5]&a…...
Android 13 Hotseat定制化修改——005 hotseat图标禁止形成文件夹
目录 一.背景 二.方案 一.背景 由于需求是需要自定义修改Hotseat,所以此篇文章是记录如何自定义修改hotseat的,应该可以覆盖大部分场景,修改点有修改hotseat布局方向,hotseat图标数量,hotseat图标大小,hotseat布局位置,hotseat图标禁止形成文件夹,hotseat图标禁止移动…...
插入、希尔、归并、快速排序(java实现)
目录 插入排序 希尔排序 归并排序 快速排序 插入排序 排序原理: 1.把所有元素分为两组,第一组是有序已经排好的,第二组是乱序未排序。 2.将未排序一组的第一个元素作为插入元素,倒序与有序组比较。 3.在有序组中找到比插入…...
怎么把图片表格转换成word表格?几个步骤达成
在处理文档时,图片表格的转换是一个常见的需求。而手动输入表格是非常耗时的,因此,使用文本识别软件来自动转换图片表格可以大大提高工作效率。在本文中,我们将介绍如何使用OCR文字识别技术来将图片表格转换为Word表格。 OCR文字识…...
多线程与高并发--------阻塞队列
四、阻塞队列 一、基础概念 1.1 生产者消费者概念 生产者消费者是设计模式的一种。让生产者和消费者基于一个容器来解决强耦合问题。 生产者 消费者彼此之间不会直接通讯的,而是通过一个容器(队列)进行通讯。 所以生产者生产完数据后扔到…...
前端-NVM,Node.js版本管理
NVM(Node Version Manager)是一个用于管理Node.js版本的工具,主要用于前端开发中。它允许开发者同时安装和切换不同版本的Node.js,以满足不同项目对Node.js版本的需求。 使用NVM可以带来以下几个好处: 多版本管理&…...
React - useEffect函数的理解和使用
文章目录 一,useEffect描述二,它的执行时机三,useEffect分情况使用1,不写第二个参数 说明监测所有state,其中一个变化就会触发此函数2,第二个参数如果是[]空数组,说明谁也不监测3,第…...
python模块 — 加解密模块rsa,cryptography
一、密码学 1、密码学介绍 密码学(Cryptography)是研究信息的保密性、完整性和验证性的科学和实践。它涉及到加密算法、解密算法、密钥管理、数字签名、身份验证等内容。 密码学中的主要概念包括: 1. 加密算法:加密算法用于将…...
【C++】速识模板(template<class T>)
一、引言 在我们学习C时,常会用到函数重载。而函数重载,通常会需要我们编写较为重复的代码,这就显得臃肿,且效率低下。 重载的函数仅仅只是类型不同,代码的复用率比较低,只要有新类型出现时,就…...
腾讯云10万日活服务器配置怎么选?费用多少?
日活10万的小程序或APP使用腾讯云服务器配置怎么选?腾讯云10万人服务器配置多少钱一年?可以选择腾讯云4核8G12M轻量应用服务器或8核16G18M服务器,云服务器CVM的话可以选择标准型S5实例,腾讯云服务器网来详细说下腾讯云日活10万服务…...
vue 使用vue-video-player加载视频(铺满容器)
vue 使用vue-video-player加载视频(铺满容器) 安装 npm install vue-video-player --savemain.js 引入 import VideoPlayer from "vue-video-player" import "video.js/dist/video-js.css" import "vue-video-player/src/custom-theme.css" i…...
OpenCV(三)——图像分割(三)
目录 6.区域生长算法 6.1 区域生长概要 6.2 区域生长原理 7.分水岭算法 7.1 分水岭算法概要...
数论复习c++
改造序列 题目描述 给定长度为 n n n的序列 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an,你可以从中删除一些数,使得删完以后的序列中,所有相邻元素之和均为偶数。请问最少需要删除多少个数? 输入格式 第一行…...
Java try-with-resources 显性 与 隐性 关闭 资源
try-with-resources 是 Java 7 引入的一个语言特性,用于简化资源管理的代码,特别是在处理需要关闭的资源(如文件、网络连接、数据库连接等)时。try-with-resources 允许您在 try 语句中声明需要关闭的资源,这些资源会在…...
Vue在页面输出JSON对象,测试接口可复制使用
效果图: 数据处理前: 数据处理后: 代码实现: HTML: <el-table height"600" :data"tableData" border style"width: 100%" tooltip-effect"dark" size"mini"><el-…...
【STM32】FreeRTOS开启后,不再进入主函数的while(1)
开启freertos后,想在主函数的while(1)中实现led的翻转,发现无法实现。 int main(void) {/* USER CODE BEGIN 1 *//* USER CODE END 1 *//* MCU Configuration--------------------------------------------------------*//* Reset of all peripherals, …...
Python+Selenium+Unittest 之selenium11--WebDriver操作方法1-常用操作
目录 1、send_keys("输入的内容") (输入文字) 2、clear() (清除元素内的内容) 3、click()(点击元素) 4、quit()关闭浏览器 5、refresh()(刷新浏览器页面) 6、set_window_size()和用 maxim…...
气液固三相线识别—Langmuir部分复现
关注 M r . m a t e r i a l , \color{Violet} \rm Mr.material\ , Mr.material...
Redis——常见数据结构与单线程模型
Redis中的数据结构 Redis中所有的数据都是基于key,value实现的,这里的数据结构指的是value有不同的类型。 当前版本Redis支持10种数据类型,下面介绍常用的五种数据类型 底层编码 Redis在实现上述数据结构时,会在源码有特定的…...
大数据-玩转数据-Flink-Transform
一、Transform 转换算子可以把一个或多个DataStream转成一个新的DataStream.程序可以把多个复杂的转换组合成复杂的数据流拓扑. 二、基本转换算子 2.1、map(映射) 将数据流中的数据进行转换, 形成新的数据流,消费一个元素并产出一个元素…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...
在WSL2的Ubuntu镜像中安装Docker
Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包: for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...
零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)
本期内容并不是很难,相信大家会学的很愉快,当然对于有后端基础的朋友来说,本期内容更加容易了解,当然没有基础的也别担心,本期内容会详细解释有关内容 本期用到的软件:yakit(因为经过之前好多期…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
Netty从入门到进阶(二)
二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架,用于…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
DAY 26 函数专题1
函数定义与参数知识点回顾:1. 函数的定义2. 变量作用域:局部变量和全局变量3. 函数的参数类型:位置参数、默认参数、不定参数4. 传递参数的手段:关键词参数5 题目1:计算圆的面积 任务: 编写一…...
