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

剑指-Offer 2021-11-25 22:32:31 2021-11-25 23:18:25 44 次浏览

概述

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);
        }
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/