当前位置:网站首页>LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值
LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值
2022-07-07 11:27:00 【小城老街】
1.题目
已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:
若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]
若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]
注意,数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。
给你一个元素值互不相同的数组 nums ,它原来是一个升序排列的数组,并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1:
输入:nums = [3,4,5,1,2]
输出:1
解释:原数组为 [1,2,3,4,5] ,旋转 3 次得到输入数组。
示例 2:
输入:nums = [4,5,6,7,0,1,2]
输出:0
解释:原数组为 [0,1,2,4,5,6,7] ,旋转 4 次得到输入数组。
示例 3:
输入:nums = [11,13,15,17]
输出:11
解释:原数组为 [11,13,15,17] ,旋转 4 次得到输入数组。
提示:
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums 中的所有整数互不相同
nums 原来是一个升序排序的数组,并进行了 1 至 n 次旋转
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
2.思路
(1)二分搜索
思路参考本题官方题解。
3.代码实现(Java)
//思路1————二分搜索
class Solution {
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
//如果 nums[left] < nums[right],则说明 nums[left...right] 之间的元素是升序的,所以最小元素就是 nums[left]
if (nums[left] < nums[right]) {
return nums[left];
}
int mid = left + (right - left) / 2;
if (nums[mid] < nums[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return nums[right];
}
}
边栏推荐
- regular expression
- 飞桨EasyDL实操范例:工业零件划痕自动识别
- Vscode编辑器ESP32头文件波浪线不跳转彻底解决
- 通过Keil如何查看MCU的RAM与ROM使用情况
- 信号强度(RSSI)知识整理
- 【学习笔记】zkw 线段树
- 聊聊伪共享
- 如何让electorn打开的新窗口在window任务栏上面
- OSI seven layer model
- Lingyunguang of Dachen and Xiaomi investment is listed: the market value is 15.3 billion, and the machine is implanted into the eyes and brain
猜你喜欢
Sample chapter of "uncover the secrets of asp.net core 6 framework" [200 pages /5 chapters]
通过Keil如何查看MCU的RAM与ROM使用情况
Cloud detection 2020: self attention generation countermeasure network for cloud detection in high-resolution remote sensing images
Smart cloud health listed: with a market value of HK $15billion, SIG Jingwei and Jingxin fund are shareholders
Blog recommendation | Apache pulsar cross regional replication scheme selection practice
为租客提供帮助
Milkdown 控件图标
迅为iTOP-IMX6ULL开发板Pinctrl和GPIO子系统实验-修改设备树文件
“新红旗杯”桌面应用创意大赛2022
MongoDB内部的存储原理
随机推荐
JS function 返回多个值
MongoDB命令汇总
Star Enterprise Purdue technology layoffs: Tencent Sequoia was a shareholder who raised more than 1billion
通过Keil如何查看MCU的RAM与ROM使用情况
Practical example of propeller easydl: automatic scratch recognition of industrial parts
[untitled]
php——laravel缓存cache
飞桨EasyDL实操范例:工业零件划痕自动识别
Users, groups, and permissions
迅为iTOP-IMX6ULL开发板Pinctrl和GPIO子系统实验-修改设备树文件
PACP学习笔记一:使用 PCAP 编程
存储过程的介绍与基本使用
【学习笔记】zkw 线段树
数字ic设计——SPI
Unity 构建错误:当前上下文中不存在名称“EditorUtility”
Read PG in data warehouse in one article_ stat
Some principles of mongodb optimization
LED light of single chip microcomputer learning notes
【无标题】
滑轨步进电机调试(全国海洋航行器大赛)(STM32主控)