首页 > 代码库 > Find Minimum in Rotated Sorted Array
Find Minimum in Rotated Sorted Array
leetcode上的一道题
题意大致是：给定一个循环移位后的排序数组，求数组的最小值
抛开假设不谈，实际上就是一个求数组最小值的问题，可以o(n)扫一遍记录最小值；也相当于求[0,vec.size()-1]的区间最小值问题，可以转化成线段树树状数组处理
本问题的假设可以利用：数组是“片段”有序的，可能出现的情况是：
1.递增-断点-递增
2.完全递增（比如循环移位数组长度的倍数次）
考虑用二分的方法解，之所以想到二分是因为用o(n)看起来这题也太简单了摔：）
而且数组是有序的，虽然是部分有序
二分
搜索区间减小的思想：
int findMin(vector<int> &num) { int size=num.size(),l=0,r=size-1,mid,min_val; if (num.empty()) { return -1; } min_val=num[0]; while (l<=r) { mid=(l+r)/2; if (num[mid]>=num[l]) { if (num[l]<min_val) { min_val=num[l]; } l=mid+1; } else{ if (num[mid]<min_val) { min_val=num[mid]; } r=mid-1; } } return min_val;}
解释一下：num[mid]>=num[l],说明[l,mid]这区间是一递增子区间，最小值是num[l]可能更新最小值，搜索区间变为[mid+1,r]
同理,num[mid]<num[l]说明[l,mid]区间有一断点，断点可能是mid或mid左的值，用num[mid]更新最小值后搜索区间变为[l,mid-1]
数值区间搜索的思想：
int findMin(vector<int> &num) { int l=0,r=num.size()-1,mid; while (l<r) { mid=(l+r)/2; if (num[mid]<num[r]) r=mid; else l=mid+1; } return num[r];}
代码很短
考虑上面两种可能出现的情况：发现无论何时num[mid]<num[r],最小值总在[l,mid]区间，num[mid]>num[r]最小值总在[mid+1,r]区间（可以笔画模拟下），当只剩一个数的时候，这个数就是最小值
Find Minimum in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。