博文中会简要介绍Leetcode P0154题目分析及解题思路。
“Find Minimum in Rotated Sorted Array II”这道题是p0153和p0081结合的变形题。
在p0081中我们要寻找特定的target并且数组中有重复。在p0153里特定的target是整个数组中的最小值但数组无重复。
本题是将这两个题目相结合。同样虽然我们无法得知最小值，但是我们依旧可以通过考虑mid与数组两端、mid两边邻居的关系来判断最小值在左半边还是右半边区间，从而二分搜索。
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]> ).
Find the minimum element.
The array may contain duplicates.
Example 1:
Input: [1,3,5] Output: 1Example 2:
Input: [2,2,2,0,1] Output: 0Note:
- This is a follow up problem to Find Minimum in Rotated Sorted Array(p0153).
- Would allow duplicates affect the run-time complexity? How and why?
这道题需要解决的核心问题在于当前mid大于等于左邻，小于等于右邻时会出现同时和左右相等的情况。这种情况下，最小值可以出现在mid左边或右边，所以需要两边搜索，此时几乎无法采用迭代的思路，而递归的解法更加简洁明了。
除此之外，这道题的follow-up中提问时间复杂度的变化，答案是最坏情况下会变为O(n)，平均时间复杂度还是O(logn)，原因是有一个情况需要两边都搜索，譬如最坏情况下只有最小值不同，其余元素都相同。这样一来每个元素最多会搜索一次，所以最多是n次搜索，即O(n)，
以下是Java的题解代码实现。
class Solution {
public int findMin(int[] nums) {
int N = nums.length;
if (nums[0] < nums[N-1])
return nums[0];
return this.binarySearch(nums, 0, N-1, N);
}
private int binarySearch(int[] nums, int left, int right, int N) {
if (right-left <= 1) {
return Math.min(nums[left], nums[right]);
}
int mid = (left+right)/2;
int leftNum = nums[mid-1];
int rightNum = nums[mid+1];
// 如果当前mid大于等于左邻，同时小于等于右邻
if (nums[mid] >= leftNum && nums[mid] <= rightNum) {
// 如果当前mid大于等于左端，同时大于右端，此时最小值在mid右边
if (nums[mid] >= nums[0] && nums[mid] > nums[N-1]) {
return this.binarySearch(nums, mid+1, right, N);
}
// 如果当前mid小于左端，同时小于等于右端，此时最小值在mid左边
else if (nums[mid] < nums[0] && nums[mid] <= nums[N-1]) {
return this.binarySearch(nums, left, mid-1, N);
}
// 如果当前mid同时等于左右两端，则两边都有可能
else {
return Math.min(this.binarySearch(nums, left, mid-1, N),
this.binarySearch(nums, mid+1, right, N));
}
}
// 当前mid恰好是最小值（同时相等的情况在上面条件里已经考虑了，则不会进入当前条件分支）
else if (nums[mid] <= leftNum && nums[mid] <= rightNum) {
return nums[mid];
}
// 如果当前mid恰好大于右邻，同时大于等于左邻
else {
return rightNum;
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
int findMin(vector<int>& nums) {
int N = nums.size();
if (nums[0] < nums[N-1])
return nums[0];
return this->_BinarySearch(nums, 0, N-1, N);
}
private:
int _BinarySearch(vector<int> &nums, int left, int right, int N) {
if (right-left <= 1) {
return min(nums[left], nums[right]);
}
int mid = (left+right)/2;
// 如果当前mid大于等于左邻，同时小于等于右邻
if (nums[mid] >= nums[mid-1] && nums[mid] <= nums[mid+1]) {
// 如果当前mid大于等于左端，同时大于右端，此时最小值在mid右边
if (nums[mid] >= nums[0] && nums[mid] > nums[N-1]) {
return this->_BinarySearch(nums, mid+1, right, N);
}
// 如果当前mid小于左端，同时小于等于右端，此时最小值在mid左边
else if (nums[mid] < nums[0] && nums[mid] <= nums[N-1]) {
return this->_BinarySearch(nums, left, mid-1, N);
}
// 如果当前mid同时等于左右两端，则两边都有可能
else {
return min(this->_BinarySearch(nums, left, mid-1, N),
this->_BinarySearch(nums, mid+1, right, N));
}
}
// 当前mid恰好是最小值（同时相等的情况在上面条件里已经考虑了，则不会进入当前条件分支）
else if (nums[mid] <= nums[mid-1] && nums[mid] <= nums[mid+1]) {
return nums[mid];
}
// 如果当前mid恰好大于右邻，同时大于等于左邻
else {
return nums[mid+1];
}
}
};