首页 > 代码库 > leetcode Find Minimum in Rotated Sorted Array
leetcode Find Minimum in Rotated Sorted Array
一个有序数组，没有重复数字，向右推进了几次，找出最小值。例如
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
直接遍历一次找到答案就没有意义了。之前做过类似的题目，不过我找不到具体的题号了。所以就随便搜了下Garnker的，知道是Search in Rotated Sorted Array，那题是找目标值。这里是找最小值。
我是这样想的，分为几部分，
1.如果左边的值等于中间的值了，那么就剩下两个数要判断了，而且是相邻的。
2.如果中间的值大于左边的值，那么最小值肯定不是在最左边就只在右边一块了。
3.如果中间值小于左边的值，那么最小值不是中间的值就是在左边一块了。
class Solution {public: int findMin(vector<int> &num) { int len = num.size(), left = 0, right = len - 1, mid = (left + right ) / 2, minmum = INT_MAX; while(left != right) { mid = (left + right) / 2; if (num[mid] == num[left]) { if (num[left] > num[right]) left = right; break; } else if (num[mid] > num[left]) { if (num[left] < minmum) minmum = num[left]; left = mid + 1; } else if (num[mid] < num[left]) { if (num[mid] < minmum) minmum = num[mid]; right = mid - 1; } } minmum = min(minmum, num[left]); // 这个不能忘 return minmum; }};
leetcode Find Minimum in Rotated Sorted Array
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。