题目描述：
给出一个长度为 $n$ 的数组，预先按照升序排列，在下标 $k$ ，经过旋转之后得到新的数组 $[nums[k], …, nums[n-1], nums[0],…, nums[k-1]]$ 。给出一个可能存在重复元素值的数组 nums，找出其中最小的元素。尽可能减少整个过程的操作步骤。与153.寻找旋转排序数组中的最小值类似，但是存在重复元素。
数据范围：
$1\le n \le 5000$
题解：
旋转之后的数组满足，观察发现前一段的都大于等于 $nums[0]$ ，后一段的都小于等于 $nums[0]$ 。或者前一段的都大于等于 $nums[n-1]$ ，后一段的都小于等于 $nums[n-1]$ 。可以根据这个进行二分搜索。
不相等的情况和前一题类似，不过如果相等的时候即 $nums[mid] = nums[r]$ ，这时需要 $r=r-1$ 。因为 $nums[r]$ 的值已经留在了 $nums[mid]$ ，后续的搜索过程不会错过该值。相等的时候并不能确定最优解在左侧或是在右侧，只能确定 $r$ 可以删掉了。
只有首尾存在相等值时才会出现判断困难的情况，也可以先移动 $r$ 直到 $nums[r]\neq nums[0]$ 。
代码：
分两段
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
| class Solution
{
public:
int findMin(vector<int> &nums)
{
int n = nums.size();
int l = 0, r = n - 1, mid;
while (l < r)
{
mid = l + r >> 1;
if (nums[mid] < nums[r])
{
r = mid;
}
else if (nums[mid] > nums[r])
{
l = mid + 1;
}
else if (nums[mid] == nums[r])
{
r--;
}
}
return nums[l];
}
};
|
分三段
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
| class Solution
{
public:
int findMin(vector<int> &nums)
{
int n = nums.size();
int l = 0, r = n - 1, mid, ans = -1;
while (l <= r)
{
mid = l + r >> 1;
if (nums[mid] < nums[r])
{
ans = mid;
if (mid - 1 >= l && nums[mid - 1] <= nums[mid])
r = mid - 1;
else
break;
}
else if (nums[mid] > nums[r])
{
l = mid + 1;
}
else if (nums[mid] == nums[r])
{
ans = mid;
r--;
}
}
return nums[ans];
}
};
|