当前位置:网站首页>【每日一题】【leetcode】25. 数组-旋转数组的最小数字
【每日一题】【leetcode】25. 数组-旋转数组的最小数字
2022-08-10 15:04:00 【aneutron】
题目
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。 难易程度:easy
示例 1:
输入:[3,4,5,1,2] 输出:1
示例 2:
输入:[2,2,2,0,1] 输出:0
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
方法一
分析
首先,题目中给出的数组是部分有序。最小的元素就是旋转点:
- 前后元素都比他大
- 前边的子数组是递增的
- 后边的子数组是递增的
因此,直观的解法就是遍历,找到第一个位置:numbers[l] < numbers[r]
。 时间复杂度:O(N) 空间复杂度:O(1)
代码
class Solution {
public:
int minArray(vector<int>& numbers) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
if (numbers[l] >= numbers[r]) {
l++;
} else {
break;
}
}
return numbers[l];
}
};
方法二
分析
题意已经明确,原始数组是由有序数组旋转生成,设最小值的索引为mid
,则[0, mid)
和[mid, size)
是两个有序数组。查找最小值本身就是搜索问题。本题题意抽取出如下两点:
- 有序
- 查找
因此,可以考虑二分搜索算法,判断条件如下;
numbers[mid] > numbers
, 则l = mid + 1
numbers[mid] < numbers
, 则r = mid
numbers[mid] == numbers
,特殊的点就在这儿,此时,最小值只能在[l, r)
,因此r--
时间复杂度:O(logN) 空间复杂度:O(1)
代码
class Solution {
public:
int minArray(vector<int>& numbers) {
int l = 0, r = numbers.size() - 1;
while (l < r) {
int mid = ((r - l) >> 1) + l;
if (numbers[mid] > numbers[r]) {
l = mid + 1;
} else if (numbers[mid] < numbers[r]) {
r = mid;
} else {
r--;
}
}
return numbers[r];
}
};
边栏推荐
猜你喜欢
Meaning and names of 12 nautical miles, 24 nautical miles and 200 nautical miles
dedecms支持Word内容自动导入
解题-->在线OJ(十九)
“低代码”编程或将是软件开发的未来
storage of data in memory
社区动态——恭喜海豚调度中国区用户组新晋 9 枚“社群管理员”
基于 Azuki 系列:NFT估值分析框架“DRIC”
QOS function introduction
fatal error C1083 Unable to open include file 'io.h' No such file
Mysql语句分析、存储引擎、索引优化等详情
随机推荐
第贰章模块大全之《 collections模块》
Pytest framework optimization
pm2之静态文件服务
一文让你快速了解大小端概念!
兆骑科创高层次人才创业大赛平台,投融资对接,双创服务
Network engineer's backpack (EDC summary recommendation)
A test tool for ABAP Development Tool custom service endpoint
自定义picker滚动选择器样式
scala集合
程序调试介绍及其使用
Yi Gene|In-depth review: epigenetic regulation of m6A RNA methylation in brain development and disease
基于 Azuki 系列:NFT估值分析框架“DRIC”
紫金示例
E. Cross Swapping(并查集变形/好题)
程序员=加班??——掌握时间才能掌握人生
Problem solving-->Online OJ (19)
Common conventions such as common SQL and API interfaces
SWIG Tutorial "One"
【教程】HuggingFace的Optimum组件已支持加速Graphcore和英特尔Habana芯片
systemui shield notification bar