首页 > 试题广场 >

旋转数组的最小数字

[编程题]旋转数组的最小数字

热度指数：1387063 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围： $1 \le n \le 10000$ ，数组中任意元素的值: $0 \le val \le 10000$

要求：空间复杂度： $O(1)$ ，时间复杂度： $O(logn)$

示例1

输入

[3,4,5,1,2]

输出

示例2

输入

[3,100,200,3]

输出

算法知识视频讲解

Maokt

发表于 2021-07-16 15:02:36

精华题解算法思想一：暴力法解题思路：主要通过对数组遍历获取最小值（此方法一般不推荐使用）算法流程： 1、特殊情况，如果数组为空，则直接返回0 2、创建最小值 minx 3、遍历数组每一个元素num，并更新最小值 minx = min(minx，num) 4、遍展开全文

牛客题解官

发表于 2022-04-22 11:42:29

精华题解题目的主要信息：有一个长度为 n 的非降序数组，把一个数组最开始的若干个元素“平移”到数组的末尾，变成一个旋转数组找到这个旋转数组的最小值举一反三：学习完本题的思路你可以解决如下题目： BM17.二分查找-I BM18.二维数组中的查找 BM19.寻找峰值方法一：二分法（推荐使用）知展开全文

漫漫云天自翱翔

发表于 2021-06-30 17:35:56

精华题解题解一：暴力搜索主要思路：从头遍历找寻最小值复杂度分析：时间复杂度：O(N)，遍历整个数组空间复杂度：O(1)，只使用常数个临时变量实现如下: class Solution { public: int minNumberInRotateArray(vec 展开全文

未来0116

发表于 2021-06-23 19:03:28

精华题解一.题目描述JZ6 旋转数组的最小数字原题链接:https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=13&&tqId=11159&rp=1&ru=/ta/coding-inte 展开全文

2019113913

发表于 2021-07-17 00:12:15

精华题解题意思路：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。方法一:暴力枚举通过遍历数组求出最小的元素复杂度分析时间复杂度：O(N)，N数组的长度，遍历数组展开全文

牛客题解官

发表于 2020-05-29 14:47:54

描述这是一道对二分查找算法灵活运用的一道题目。二分查找算法不限于运用在有序数组上。如果能够明确二分之后，答案存在于二分的某一侧，就可以使用二分。本题就是如此。难度：二星考察知识：数组，二分查找题解方法一：暴力方法：直接遍历一遍数组，即可找到最小值。但是本题的附加条件就没有用上。肯定不是面试展开全文

Ariser.cn

发表于 2019-08-19 20:32:18

参考解答区“leetcold”的解答，进行图示分析分析：二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。处于递增：low上移处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值）其余情况：low 展开全文

没有人比我更菜

发表于 2019-12-04 14:29:15

题目大意一个非递减的排序数组，从某个地方进行旋转，要找到原数组中最小的元素。解法几个月前写了一个题解，被其他同学找出了很多漏洞，当时考虑问题不够全面，另外牛客网上的测试用例也比较少，很多错误没有被发现，这次根据评论区的反馈，做了一个彻底的修改。首先举两个例子，下图中左边两幅是非递减数组绘制的展开全文

罅隙·

发表于 2022-01-14 12:29:50

解题思路 1)为什么想到二分查找？二分查找的本质的本质是二段性，只要满足二段性的问题都可以使用二分查找求解。在本题中二分查找的二段性体现在：最小值左边的单调增，最小值右边的单调增。且左边的元素都大于右边的元素。 2)如何解决分段单调的问题？很简单，我们只需要比对arr[mid]与arr 展开全文

中工升达预备毕业生

发表于 2019-08-31 09:27:36

1.offer书上的写法，坑点很多。 3 4 5 1 2 （一般情况） 1 2 3 4 5 / 2 2 2 2 2（容易想到的点） 1 0 1 1 1 / 1 1 1 0 1（扑街） public class Solution { public int minNumberInRotate 展开全文

炸掉地球

发表于 2022-01-30 15:27:40

只要出现降序则出现了最小值比如[4,5,1,2,3] ：5到1是降序，则1就是最小值；如果没出现降序，说明没旋转，则第一个数就是最小值。 int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) { int i=0 展开全文

Oh~Sunny

发表于 2020-02-10 13:11:18

此题大家如有想到的方法就是直接进行顺序的查找,复杂度为O(n).但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).这里我们需要利用带有条件的二分法来进行求解: 第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = ( 展开全文

xixiran001ya

发表于 2021-08-13 01:13:31

思路二分查找，题目的意思就是查找当前数组中最小值。二分查找，左边界值一定小于或等于右边界值，所以此题的解法就是不断挪动左右双指针，直到右指针小于左指针时结束查找，此时的左指针指向的数便是数组最小值。结果运行时间：71ms占用内存：14512KB 代码 public int minNumberIn 展开全文