剑指 Offer 11 旋转数组的最小数字

    
        标签：
        
            剑指 Offer
        
    发布于：2021-11-25 22:32:31
    编辑于：2021-11-25 23:18:25
    浏览量：973

概述

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/ 标记为简单。

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/ 标记为中等。

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/ 标记为困难。

认真的吗？

暴力遍历法

O(n) 的时间复杂度。这里就不给出代码了。

递归法

要特别注意数组中只有一个值与其他值不同的情况。

理想情况下，没有重复元素时，O(logn)；

最坏情况下，全部都是重复元素，O(n)（此时 helper 函数被执行了 2n 次）。

class Solution {
public:
    int findMin(vector<int>& nums) {
        return helper(nums, 0, nums.size() - 1);
    }

    int helper(vector<int>& nums, int l, int r) {
        int m = (l + r) / 2;
        if (m == l) return min(nums[l], nums[r]);
        if (nums[m] == nums[l] && nums[m] == nums[r]) {
            return min(helper(nums, l, m-1), helper(nums, m+1, r));
        }
        if (nums[m] >= nums[l]) {
            return min(helper(nums, m, r), nums[l]);
        } else {
            return helper(nums, l, m);
        }
    }
};

Links: sword-offer-11