带有重复元素的旋转数组的处理

上一道题目,没注意,原来不能重复:

http://www.cnblogs.com/charlesblc/p/6444027.html

而且用上一道题目来找到旋转起始位置的代码,对于有重复元素,是不可行的。

下面这道题目,专门针对有重复元素的情况:

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/?tab=Description

那么结合提示,我改了一下之前帖子的代码,得到下面的代码,通过了。好好总结。

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] < nums[hi]) {
                hi = mid;
            }
            else if (nums[mid] > nums[hi]){
                lo = mid + 1;
            }
            else {
                hi--;
            }
        }
        return nums[lo];
    }
};

最后哪个hi--真的非常的精妙。

原文地址:https://www.cnblogs.com/charlesblc/p/6451503.html