154寻找旋转排序数组中的最小值II

title: 寻找旋转排序数组中的最小值II

题目描述

解题思路

和上题同理：数组特点有 nums[mid] < nums[right]，最小值肯定在mid左边，nums[mid] > nums[right]，最小值肯定在mid右边，但是 nums[mid] = nums[right]的时候，可能在左边也在右边，如[0,1,1,1,1]、[1,1,1,0,1]，可以剪掉right

    int findMin(vector<int>& nums) {

        int left = 0, right = nums.size() - 1;

        int mid;

        while (left < right) {

            mid = left + ((right - left) >> 1);

            if (nums[mid] > nums[right]) left = mid + 1;

            else if (nums[mid] < nums[right]) right = mid;

            else  right--;//证明左边都是同一个数字，可以砍掉最右的那个位置

        }

        return nums[left];

    }

复杂度分析

空间复杂度：o(logn)
时间复杂度：O(1)

巴特西

154寻找旋转排序数组中的最小值II

题目描述

解题思路

复杂度分析

最新文章

热门文章