LeetCode: 154. Find Minimum in Rotated Sorted Array II

题目描述

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: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Note:

This is a follow up problem to Find Minimum in Rotated Sorted Array.
Would allow duplicates affect the run-time complexity? How and why?

题目大意： 求出经过旋转的有序数组的最小值（数组中含有重复元素）

解题思路 —— 折半查找

旋转后的数组有一下几种可能，其中 [beg, end) 是查找 nums 数组的最小值的区间， mid=(beg+end)/2：

• nums[mid] == nums[beg] && nums[beg] >= nums[end-1]: 最小值可能在 mid 的左边，也可能在 mid 的右边。
  （1） 最小值在 mid 左边：
  
  （2） 最小值在 mid 右边：
  

• nums[mid] < nums[beg] && nums[beg] >= nums[end-1]: 最小值在 mid 的左边。
  

• nums[mid] > nums[beg] && nums[beg] >= nums[end-1]: 最小值在 mid 的右边。
  

• 其他(升序)：最小值在最左边(nums[beg])。
  

AC 代码

class Solution {
private:
    // 返回 nums 区间 [beg, emd) 的最小值
    int findMin(const vector<int>& nums, int beg, int end)
    {
        if(beg >= end) return INT_MAX;
        if(beg + 1 == end) return nums[beg];

        int mid = (beg+end)/2;

        // nums[mid] == nums[beg] >= nums[end-1] 的情况, 最小值可能在 mid 左边和右边
        // (1) 1 1 1 1 1 1, mid = (0+6)/2
        // (2) 1 1 1 1 0 1, mid = (0+6)/2
        // (3) 1 2 0 1 1 1, mid = (0+6)/2
        if(nums[mid] == nums[beg] && nums[beg] >= nums[end-1])
        {
            return min(findMin(nums, beg, mid), findMin(nums, mid, end));
        }
        // nums[mid] > nums[beg] >= nums[end-1] 的情况， 最小值在 mid 的右边
        // 1 1 2 3 0 1, mid = (0+6)/2
        else if(nums[mid] > nums[beg] && nums[beg] >= nums[end-1])
        {
            if(beg == mid) return nums[beg];
            return findMin(nums, mid, end);
        }
        // nums[mid] < nums[beg] >= nums[end-1] 的情况， 最小值在 mid 左边
        // 1 2 3 0 1 2, mid = (0+6)/2
        else if(nums[mid] < nums[beg] && nums[beg] >= nums[end-1])
        {
            if(mid == end-1) return nums[mid];
            return findMin(nums, beg, mid+1);
        }
        // 其他（升序）： nums[beg] < nums[mid] < nums[end]
        else
        {
            return nums[beg];
        }
    }
public:
    int findMin(vector<int>& nums) {
        return findMin(nums, 0, nums.size());
    }
};