(剑指Offer)面试题8:旋转数组的最小数字
2023-09-14 08:59:06 时间
题目:
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
思路:
1、遍历数组,找到数组的最小值,时间复杂度O(n);
2、二分查找,时间复杂度O(logn)
注意旋转数组的循环不变量,A[left]>=A[right](这道题的数组为非递减数组,并非严格的递增数组)
特例:无旋转情况以及{0,1,1,1,1,1}旋转数组
查找过程:
旋转数组可以看成两个递增(非减)数组,通过前后两个指针left,right分别指向数组的首尾,
当满足循环不变量时A[left]>=A[right],mid=(left+right)/2,
如果A[mid]>=A[left],说明最小值存在mid后面部分,left=mid;
如果A[mid]<=A[left],说明最小值存在mid前面部分,right=mid;
经过循环之后,最终left会指向第一个递增数组的最后一个数,right会指向第二个递增数组的第一个数,即最小值mid=right。
最终return A[mid];
解决特例问题:
- 无旋转数组:数组就是递增的,返回第一个数,即A[left],因此mid=left即可;
- {0,1,1,1,1,1}类似旋转数组:不满足上述查找过程,只能遍历数组。
代码:
#include <iostream> #include <vector> using namespace std; int MinInOrder(int* arr,int left,int right){ int result=arr[left]; for(int i=left+1;i<=right;i++){ if(result>arr[i]) result=arr[i]; } return result; } int Min(int* numbers,int length){ if(numbers==NULL || length<=0) return -1; int left=0; int right=length-1; int mid=left; while(numbers[left]>=numbers[right]){ if(right-left==1){ mid=right; break; } mid=left+((right-left)>>1); if(numbers[left]==numbers[right] && numbers[left]==numbers[mid]) return MinInOrder(numbers,left,right); if(numbers[mid]>=numbers[left]) left=mid; else right=mid; } return numbers[mid]; } int main() { int A[]={1,0,1,1,1,1,1,1}; int len=sizeof(A)/sizeof(A[0]); Solution s; vector<int> nums(A,A+len); cout<<s.minNumberInRotateArray(nums)<<endl; cout<<Min(A,len)<<endl; return 0; }
在线测试OJ:
http://www.nowcoder.com/books/coding-interviews/9f3231a991af4f55b95579b44b7a01ba?rp=1
AC代码:
class Solution { public: int minNumberInRotateArray(vector<int> rotateArray) { int len=rotateArray.size(); if(len==0) return 0; int left=0; int right=len-1; int mid=left; //if(rotateArray[left]<rotateArray[right]); // return rotateArray[left]; while(rotateArray[left]>=rotateArray[right]){ if(right-left==1){ mid=right; break; } mid=left+((right-left)>>1); if(rotateArray[left]==rotateArray[right] && rotateArray[left]==rotateArray[mid]) return MinInOrder(rotateArray,left,right); if(rotateArray[mid]>=rotateArray[left]) left=mid; else right=mid; } return rotateArray[mid]; } int MinInOrder(const vector<int> &arr,int left,int right){ int result=arr[left]; for(int i=left+1;i<=right;i++){ if(result>arr[i]) result=arr[i]; } return result; } };
相关文章
- 挑战10个最难的Java面试题(附答案)【上】
- 208道最常见的Java面试题整理(面试必备)
- Java实习生面试题整理
- (剑指Offer)面试题3:二维数组中的查找
- (剑指Offer)面试题38:数字在排序数组中出现的次数
- (剑指Offer)面试题33:把数组排成最小的数
- JavaScript面试题-数组中最大差值
- 2022年Android秋招太难了,还好有这份面试题
- Android面试复习框架及题型解析,最新Android中高级面试题合集
- PHP面试题:在PHP中error_reporting这个函数有什么作用?
- PHP面试题:使用PHP描述快速排序算法,对象可以是一个数组?
- PHP面试题:合并两个数组有几种方式,试比较它们的异同
- PHP面试题:请写一段程序,在服务器创建一个文件fruit.dat,将试题3中得到的数组写入到改文件中,然后写一段程序从文件中读取并还原数组@author zhuwenqiong
- PHP面试题:请以空格作为间隔,拆分字符串’Apple Orange Banana Strawberry’,组成数组$fruit,
- Spring常见面试题(13个面试题,回答超详细)
- 面试题 10.01. 合并排序的数组
- 【软件测试入门学习】linux面试题与答案
- 某企业面试题汇总
- java经典面试题之Spring Boot 面试题汇总附答案(史上最全持续更新)
- React常见面试题