首页 > 试题广场 > 旋转数组的最小数字
[编程题]旋转数组的最小数字
  • 热度指数:936617 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。
头像 牛客官方题解
发表于 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
题目大意 一个非递减的排序数组,从某个地方进行旋转,要找到原数组中最小的元素。 解法 几个月前写了一个题解,被其他同学找出了很多漏洞,当时考虑问题不够全面,另外牛客网上的测试用例也比较少,很多错误没有被发现,这次根据评论区的反馈,做了一个彻底的修改。 首先举两个例子,下图中左边两幅是非递减数组绘制的 展开全文
头像 中工升达预备毕业生
发表于 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 展开全文
头像 把牛妹带回家
发表于 2019-07-26 15:43:41
直接找最小值 # -*- coding:utf-8 -*- class Solution: def minNumberInRotateArray(self, rotateArray): # write code here return min(rotateAr 展开全文
头像 铁柱锈死了
发表于 2020-02-10 13:11:18
此题大家如有想到的方法就是直接进行顺序的查找,复杂度为O(n).但是我们看到题中是给出的有序的旋转数组,我们可以采用二分法来进行求解,其复杂度为O(logn).这里我们需要利用带有条件的二分法来进行求解: 第一步我们可以将这个旋转的数组看作是前后两个有序的子数组,然后设定我们的中间值 mid = ( 展开全文
头像 无终の旅
发表于 2019-08-23 17:10:40
import java.util.ArrayList;public class Solution { public int minNumberInRotateArray(int [] array) { if(array.length>1){ for(i 展开全文
头像 心谭
发表于 2019-12-25 14:38:02
【2种解法】【剑指Offer】【JavaScript题解】 题目描述 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为 1。 NOTE:给 展开全文
头像 橙子爱吃桃子
发表于 2020-04-24 11:51:54
C++/二分法/代码: class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { vector<int> nums = rotateArray; 展开全文
头像 南大一汀烟雨
发表于 2020-05-09 02:07:36
//题目描述//把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。//输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。//例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。//NOTE:给出的所有元素都大于0,若数组大小为0,请返回0 展开全文
头像 鹿贤惠
发表于 2020-04-10 22:26:08
有这样的一个思路:设置一个参数i另一个参数i+1,这样就成了一个前面的一个后面的,如果后面的比前面的小那么一定就是后面的这个元素是最小值。因为旋转之后是部分部分的非递减的。就算是10111这样的例子,第一次判断0是小于1的直接就返回0可以了。import java.util.ArrayList;pu 展开全文