首页 > 代码库 > Leetcode#154 Find Minimum in Rotated Sorted Array II
Leetcode#154 Find Minimum in Rotated Sorted Array II
原题地址
说个题外话，我一直想不明白题目里rotate这个词，感觉用shift更合适啊
仔细分析题目，有如下两个性质：
1. 对于一个没有折叠过的数组，最小值一定是第一个元素。
2. 对于一个折叠过的数组，最小值一定出现在折叠的地方。
因此，要找最小值，就把以上两种情况下的最小值都看看，选一个最小的就行了。这样理解的话比较好写代码。
唯一的问题是，如何判断一个数组是否已经折叠过了？假设数组的左边界是left，右边界是right
1. 如果left < right，则说明数组一定是连续的（没有折叠过）
2. 如果left > right，则说明数组一定不是连续的（折叠过）
3. 如果left = right，没法判断，因为折叠过和没折叠过都可能产生这种结果。
前两种情况很好判断，第三种情况怎么办呢？其实没有什么办法，只能一个一个比，但是只要发现任何一个不一样的元素就说明不连续。
剩下的就比较简单了，用二分搜索的方式逐步缩小范围
时间复杂度分析：最坏情况下，所有元素都相等，这时退化成O(n)，否则其他情况下为O(log(n))。
代码：
1 // 判断区间单调性 2 bool monop(vector<int> &num, int l, int r) { 3 if (num[l] != num[r]) 4 return num[l] < num[r]; 5 6 while (l < r && num[l] == num[r]) 7 l++; 8 9 return l == r;10 }11 12 int findMin(vector<int> &num) {13 int l = 0;14 int r = num.size() - 1;15 int minEle = num[0];16 17 while (l <= r) {18 int m = (l + r) / 2;19 if (monop(num, l, m)) {20 minEle = min(minEle, num[l]);21 l = m + 1;22 }23 else {24 minEle = min(minEle, num[m]);25 r = m - 1;26 }27 }28 29 return minEle;30 }
Leetcode#154 Find Minimum in Rotated Sorted Array II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。