-
Notifications
You must be signed in to change notification settings - Fork 4
/
160_findMin.cpp
68 lines (59 loc) · 1.44 KB
/
160_findMin.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
160 寻找旋转排序数组中的最小值 II
假设一个旋转排序的数组其起始位置是未知的(比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2)。
你需要找到其中最小的元素。
数组中可能存在重复的元素。
样例
给出[4,4,5,6,7,0,1,2] 返回 0
*/
class Solution {
public:
/**
* @param num: a rotated sorted array
* @return: the minimum number in the array
*/
int findMin(vector<int> &num) {
// write your code here
if(num.empty())
{
return -1;
}
int len = num.size();
int lhs = 0, rhs = len-1;
while(num[lhs] >= num[rhs])
{
if(rhs - lhs == 1)
{
return num[rhs];
}//if
int mid = (lhs + rhs) / 2;
if(num[lhs] == num[rhs] && num[lhs] == num[mid])
{
return midInorder(num, lhs, rhs);
}
if(num[mid] >= num[lhs])
{
lhs = mid;
}else if(num[mid] <= num[rhs]){
rhs = mid;
}
}
return num[lhs];
}
int midInorder(vector<int> &num, int lhs, int rhs)
{
if(num.empty() || lhs <0 || rhs >= num.size())
{
return -1;
}
int ret = num[lhs];
for(int i=lhs+1; i<=rhs; ++i)
{
if(ret > num[i])
{
ret = num[i];
}
}
return ret;
}
};