[LeetCode]154.Find Minimum in Rotated Sorted Array II
【题目】
Follow upfor "Find Minimum in Rotated Sorted Array":
What ifduplicatesare allowed?Would this affect the run-time complexity? How and why?
Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e.,0 1 2 4 5 6 7
might become4
5 6 7 0 1 2
).
Find the minimum element.
The array may contain duplicates.
【分析】
这一道题是上一道题的拓展延伸:[LeetCode]153.Find Minimum in Rotated Sorted Array
上一道题目说明没有重复数字,这一道题目添加上了这一要求,有了重复数字。
因此这一道题目比上一道题目多了些特殊情况:
我们看一组例子:{1,0,1,1,1} 和 {1,1,1,0,1} 都可以看成是递增排序数组{0,1,1,1,1}的旋转。
这种情况下我们无法继续用上一道题目的解法,去解决这道题目。因为在这两个数组中,第一个数字,最后一个数字,中间数字都是1。
第一种情况下,中间数字位于后面的子数组,第二种情况,中间数字位于前面的子数组。
因此当两个指针指向的数字和中间数字相同的时候,我们无法确定中间数字1是属于前面的子数组(绿色表示)还是属于后面的子数组(紫色表示)。
也就无法移动指针来缩小查找的范围。
【代码】
/*********************************
* 日期:2015-01-31
* 作者:SJF0115
* 题目: 154.Find Minimum in Rotated Sorted Array II
* 网址:https://oj.leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int findMin(vector<int> &num) {
int left = 0,right = num.size() - 1;
int mid = 0;
// num[left] >= num[right] 确保旋转
while(num[left] >= num[right]){
// 分界点
if(right - left == 1){
mid = right;
break;
}//if
mid = left + (right - left) / 2;
// num[left] num[right] num[mid]三者相等
// 无法确定中间元素是属于前面还是后面的递增子数组
// 只能顺序查找
if(num[left] == num[right] && num[left] == num[mid]){
return MinOrder(num,left,right);
}//if
// 中间元素位于前面的递增子数组
// 此时最小元素位于中间元素的后面
if(num[mid] >= num[left]){
left = mid;
}//if
// 中间元素位于后面的递增子数组
// 此时最小元素位于中间元素的前面
else{
right = mid;
}
}//while
return num[mid];
}
private:
// 顺序寻找最小值
int MinOrder(vector<int> &num,int left,int right){
int result = num[left];
for(int i = left + 1;i < right;++i){
if(num[i] < result){
result = num[i];
}//if
}//for
return result;
}
};
int main(){
Solution solution;
//vector<int> num = {0,1,2,3,4,5};
vector<int> num = {1,0,1,1,1,1,1};
int result = solution.findMin(num);
// 输出
cout<<result<<endl;
return 0;
}
【代码二】
class Solution {
public:
int findMin(vector<int> &num) {
int left = 0,right = num.size() - 1;
int mid = 0;
while(left < right){
mid = left + (right - left) / 2;
if(num[mid] > num[right]){
left = mid + 1;
}//if
else if(num[mid] < num[right]){
right = mid;
}//else
// 不能确定最小元素在哪边
else{
--right;
}
}//while
return num[left];
}
};