题目描述:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如数组{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
采用二分查找的策略,重点要考虑一些边界情况:旋转了0元素,即输入的是一个升序排列的数组、只包含一个数字的数组、有很多重复数字的数组等。
#include<stdio.h>
#include<stdlib.h>
int MinInOrder(int*,int,int);
int min(int *numbers,int length)
{
if(numbers==NULL||length<=0)
return 0;
int index1=0;
int index2=length-1;
int indexMid=index1;
while(numbers[index1]>=numbers[index2])
{
if(index2-index1==1)
{
indexMid=index2;
break;
}
indexMid=(index1+index2)/2;
//如果下标为index1,index2和indexMid 指向的三个数字相等
//则只能顺序查找
if(numbers[index1]==numbers[index2]&&numbers[index1]==numbers[indexMid])
return MinInOrder(numbers,index1,index2);
if(numbers[indexMid]>=numbers[index1])
index1=indexMid;
if(numbers[indexMid]<=numbers[index2])
index2=indexMid;
}
return numbers[indexMid];
}
int MinInOrder(int* numbers,int index1,int index2)
{
int result=numbers[index1];
for(int i=index1+1;i<=index2;++i)
{
if(result>numbers[i])
result=numbers[i];
}
return result;
}
int main()
{
int number;
while(scanf("%d",&number)!=EOF)
{
int *numbers=(int*)malloc(number*sizeof(int));
int i;
for(i=0;i<number;i++)
scanf("%d",numbers+i);
int result=min(numbers,number);
printf("%d\n",result);
}
return 0;
}
结果:
分享到:
相关推荐
哈工大算法实验二,最长公共子序列问题,动态规划解决LCS 1.实现基于优化子结构的递归求解算法 2.实现基于动态规划的求解算法 3.实现三个字符串最长公共子序列的动态规划算法 4.有界面源代码和实验报告!...
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出数组的最小元素。...例如:数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{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}的...
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 解题思路参考博客
面试题:旋转数组的最小数字 题目:把一个数组的最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增数组的旋转,输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组...
寻找旋转排序数组中的最小值.md
寻找旋转排序数组中的最小值 II.md
剑指Offer(Python多种思路实现):旋转数组的最小数字 题目: 把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1...
寻找旋转排序数组中的最小值 提示 已知一个长度为 n 的数组,预先按照升序排列,经由 1 到 n 次 旋转 后,得到输入数组。例如,原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到: 若旋转 4 次,则可以得到 [4,5,...
python python_leetcode面试题解之第153题寻找旋转排序数组中的最小值_题解
python python_leetcode面试题解之第154题寻找旋转排序数组中的最小值II_题解
例如数组{3,4,5,1,2}是数组{1,2,3,4,5}的旋转数组,该数组的最小值为1。 思路解析: O(N)的算法 这种算法的思想就是遍历这个数组,由于这个数组是两部分有序的数组,因此遍历这个数组时当后一个数字小于前一个数字...
153. 寻找旋转排序数组中的最小值1.二分法如果 nums[mid] 小于最后一个数,最小值一定在最后一个数左面如果 nums[mid] 在左侧上升序列,最小
旋转数组最小值 孩子们的游戏 二叉树的下一个结点 数据流中的中位数 使用两个优先级队列来处理流,队列的排序方向不一致 滑动窗口的最大值 维持一个窗口 大小 同时从右往左获取窗口的左边界的最大值 机器人的运动...
例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。输入:[3,4,5,1,2]输出:1输入:[2,2,2,0,1]
则此时无法区分最小值是在数组的左半部分还是右半部分(例如:{2,2,2,2,1,2},{2,1,2,2,2,2,2})在这种情况下,只能分别在数组的左右两部分找
输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 1、利用二分法寻找数组...
如果 nums[mid] > nums[right],则最小值不可能在 mid 左侧,一定在 mid 右侧,则将 left 移动到 mid + 1 位置,继续查
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。示例 1:输入: [3,4,5,1,2]输出: 1示例 2:输入:
153.旋转数组最小值0513 162.寻找峰值0513 2.2、单调队列 496 下一个更大元素 I (模板题) 42 接雨水(单调栈,还是不会) 84 柱状图中最大的矩形(单调栈)失败ing 单调栈模板 外面for循环,里面while循环。 单调栈...