当前位置:网站首页>LeetCode_ Binary search_ Medium_ 153. Find the minimum value in the rotation sort array
LeetCode_ Binary search_ Medium_ 153. Find the minimum value in the rotation sort array
2022-07-07 13:22:00 【Old street of small town】
1. subject
We know a length of n Array of , In ascending order in advance , Through 1 To n Time After rotation , Get the input array . for example , Original array nums = [0,1,2,4,5,6,7] After the change may get :
If you rotate 4 Time , You can get [4,5,6,7,0,1,2]
If you rotate 7 Time , You can get [0,1,2,4,5,6,7]
Be careful , Array [a[0], a[1], a[2], …, a[n-1]] Rotate once The result is an array [a[n-1], a[0], a[1], a[2], …, a[n-2]] .
Give you an element value Different from each other Array of nums , It turns out to be an ascending array , According to the above situation, we have made many rotations . Please find and return the smallest element in the array .
You have to design a time complexity of O(log n) The algorithm to solve this problem .
Example 1:
Input :nums = [3,4,5,1,2]
Output :1
explain : The original array is [1,2,3,4,5] , rotate 3 Get the input array for the first time .
Example 2:
Input :nums = [4,5,6,7,0,1,2]
Output :0
explain : The original array is [0,1,2,4,5,6,7] , rotate 4 Get the input array for the first time .
Example 3:
Input :nums = [11,13,15,17]
Output :11
explain : The original array is [11,13,15,17] , rotate 4 Get the input array for the first time .
Tips :
n == nums.length
1 <= n <= 5000
-5000 <= nums[i] <= 5000
nums All integers in are different from each other
nums It turns out to be an ascending array , And carried on 1 to n Second rotation
source : Power button (LeetCode)
link :https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array
2. Ideas
(1) Two point search
Train of thought reference Official solution to this problem .
3. Code implementation (Java)
// Ideas 1———— Two point search
class Solution {
public static int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
// If nums[left] < nums[right], shows nums[left...right] The elements between are in ascending order , So the smallest element is 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];
}
}
边栏推荐
- How to make the new window opened by electorn on the window taskbar
- OSI 七层模型
- ORACLE进阶(五)SCHEMA解惑
- ESP32系列专栏
- MySQL master-slave replication
- DHCP 动态主机设置协议 分析
- centso7 openssl 报错Verify return code: 20 (unable to get local issuer certificate)
- LeetCode_二分搜索_中等_153.寻找旋转排序数组中的最小值
- 记一次 .NET 某新能源系统 线程疯涨 分析
- [learning notes] zkw segment tree
猜你喜欢
Sequoia China completed the new phase of $9billion fund raising
About how appium closes apps (resolved)
OSI seven layer model
Introduction and basic use of stored procedures
【Presto Profile系列】Timeline使用
Aosikang biological sprint scientific innovation board of Hillhouse Investment: annual revenue of 450million yuan, lost cooperation with kangxinuo
Practical example of propeller easydl: automatic scratch recognition of industrial parts
Vscode编辑器ESP32头文件波浪线不跳转彻底解决
为租客提供帮助
日本政企员工喝醉丢失46万信息U盘,公开道歉又透露密码规则
随机推荐
JS determines whether an object is empty
QQ medicine, Tencent ticket
信号强度(RSSI)知识整理
记一次 .NET 某新能源系统 线程疯涨 分析
Mongodb command summary
DHCP 动态主机设置协议 分析
Isprs2021/ remote sensing image cloud detection: a geographic information driven method and a new large-scale remote sensing cloud / snow detection data set
将数学公式在el-table里面展示出来
User management summary of mongodb
Sequoia China completed the new phase of $9billion fund raising
【黑马早报】华为辟谣“军师”陈春花;恒驰5预售价17.9万元;周杰伦新专辑MV 3小时播放量破亿;法华寺回应万元月薪招人...
[untitled]
Mongodb replication (replica set) summary
【学习笔记】zkw 线段树
Aosikang biological sprint scientific innovation board of Hillhouse Investment: annual revenue of 450million yuan, lost cooperation with kangxinuo
【学习笔记】AGC010
日本政企员工喝醉丢失46万信息U盘,公开道歉又透露密码规则
详细介绍六种开源协议(程序员须知)
JS function 返回多个值
Read PG in data warehouse in one article_ stat