题目1386：旋转数组的最小数字
题目描述：
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
输入：
输入可能包含多个测试样例，对于每个测试案例，
输入的第一行为一个整数n(1<= n<=1000000)：代表旋转数组的元素个数。
输入的第二行包括n个整数，其中每个整数a的范围是(1<=a<=10000000)。
输出：
对应每个测试案例，
输出旋转数组中最小的元素。
样例输入：
53 4 5 1 2
样例输出：
1
/*********************************
* 日期：2013-11-14
* 作者：SJF0115
* 题号: 题目1386：旋转数组的最小数字
* 来源：http://ac.jobdu.com/problem.php?pid=1386
* 结果：AC
* 来源：剑指Offer
* 总结：
**********************************/
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
int array[1000001];
//求旋转数组最小值
int MInArray(int *array,int n){
int left = 0;
int right = n - 1;
int mid = 0;
//二分查找最小值
while(array[left] >= array[right]){
//如果相邻right下标为最小值
if(right - left == 1){
mid = right;
break;
}
mid = (left + right) / 2;
//如果下标为left,right,mid的数值相等，只能顺序查找
if(array[left] == array[right] && array[left] == array[mid]){
int min = array[left];
//顺序查找最小值
for(int i = left + 1;i <= right;i++){
if(min > array[i]){
min = array[i];
}
}
return min;
}
//mid 处于第一递增排序序列 最小值在mid后面
if(array[mid] >= array[left]){
left = mid;
}
//mid 处于第二递增排序序列 最小值在mid前面
else if(array[mid] <= array[right]){
right = mid;
}
}
return array[mid];
}
int main()
{
int i,n;
while(scanf("%d",&n) != EOF){
for(i = 0;i < n;i++){
scanf("%d",&array[i]);
}
printf("%d\n",MInArray(array,n));
}
return 0;
}
天猫搞活动。。。。。。。。
我在用来往，用它我们就能免费语聊！11月1日到11月9日用淘宝账号登陆我还能送你2元双11现金红包！我在来往上叫sjf0115，搜索下sjf0115来找我聊天吧！点击
![]()
点击打开链接,赶紧拿红包吧！
分享到：
相关推荐
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 概念回顾 二分法 ...
题目位置题解* 思路* 1、找到数组中元素最小的元素public int minArray(int[] numbers) {
例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。输入：[3,4,5,1,2]输出：1输入：[2,2,2,0,1]
例如 [1, 0, 1, 1, 1] 和 [1, 1, 1, 0, 1] ，在 left = 0, right = 4, mid = 2 时，无法判断 mid
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 解题思路参考博客
剑指Offer(Python多种思路实现):旋转数组的最小数字 题目： 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1...
《剑指Offer》 1. 赋值运算函数 2. 单例设计模式 3. 二维数组中查找目标值 4. 替换字符串中的空格 5. 从尾到头打印链表 6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. ...
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 又例如｛1,0,1,1,1｝和｛1,1,1,0,1｝都可以看成是递增排序数组｛0,1,1,1,1｝的...
面试题 6：旋转数组的最小数字(考点：查找和排序) 6 面试题 7：斐波那契数列(考点： 递归和循环) 7 面试题 8：跳台阶(考点： 递归和循环) 7 面试题 9：变态跳台阶(考点： 递归和循环) 8 面试题 10：矩形覆盖(考点...
旋转数组的最小数字 简单 剑指offer12 矩阵钟的路径 中等 剑指offer13 机器人的运动范围 中等 剑指offer14-1 剪绳子 中等 剑指offer14-2 剪绳子Ⅱ 中等 剑指offer15 二进制中1的个数 简单 剑指offer16 数值的整数...
剑指offer_Python版数组篇1.二维数组中的查找6.旋转数组中的最小值11.调整数组使奇数位于偶数前面19.顺时针打印矩阵28.数组中出现次数超过一半的数字30.连续子数组最大和32.把数组排出最小的数35.数组中的逆序对37....
面试题8 旋转数组的最小数字 面试题9 斐波那契数列 面试题10 二进制中1的个数 第3章 高质量代码 3.3 代码的完整性 面试题11 数值的整数次方 面试题12 打印1到最大的n位数 面试题13 O(1)时间删除链表结点 面试题14 ...
旋转数组的最小数字 Y Y Y 剑指 Offer 14- I. 剪绳子 Y Y Y 剑指 Offer 15. 二进制中1的个数 Y Y Y 剑指 Offer 17. 打印从1到最大的n位数 Y Y Y 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 Y Y Y 剑指 Offer 24...
leetcode 剑指 Offer 50 道经典算法题视频讲解 「剑指 Offer」是何海涛写的一本算法面试书，书中...旋转数组的最小数字 - - leetcode 153 | lintcode 159 斐波那契数列 - - leetcode 509 | lintcode 366 二进制中 1 的
面试题08：旋转数组中的最小数 面试题10：二进制中1的个数 面试题14：调整数组顺序使奇数位于偶数前面 面试题18：树的子结构 面试题20：顺时针打印矩阵 面试题21：最小栈 面试题26：复杂链表的复制 面试题31：连续...
旋转数组的最小数字 -> √矩阵中的路径 -> 机器人的运动范围 -> 没找到 -> （中文版） 剪绳子（dp） -> √二进制中1的个数 -> ->（升级版） √数值的整数次方（溢出） -> 打印从1到最大的n位数（溢出） -> 没找到 √...
11 旋转数组的最小数字 12 矩阵中的路径 13 机器人的运动范围 14 剪绳子 15 二进制中1的个数 第3章 高质量的代码 3.3 代码的完整性 16 数值的整数次方 17 打印从1到最大的n位数 18 删除链表中的节点 19 正则表达式 ...
旋转数组的最小数字 查找和排序 LeetCode 153 7 斐波那契数列 递归和循环 LeetCode 509 8 跳台阶 递归和循环 LeetCode 70 9 变态跳台阶 递归和循环 10 矩形覆盖 递归和循环 11 二进制中1的个数 位运算 LeetCode 191 ...
leetcode中文版 剑指Offer的Python解答 剑指Offer的Python解答，不断更新。如果数学公式无法正确显示，可以clone到本地查看...旋转数组的最小数字 二分法 矩阵中的路径 dfs 机器人的运动范围 dfs，bfs 剪绳子 数学，动