lc.153 无重复数字找最小值

思路

• 画图找到关键点
• 排序数组旋转后会形成两段单调递增的直线
• 然后根据mid和nums[n-1]的大小去找答案，每次二分时一定要保证答案在区间内

时间复杂度(O(logn)

/**
* 不存在重复数字
* 画图-> 二分
*/
class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums[n-1])
                r = mid;
            else
                l = mid + 1;
        }
        return nums[r];
    }
}

lc.154 寻找旋转排序数组最小值II(有重复数组)

思路

• 画图分析
  • 在排序数组中重复的数一定是连续的一段
  • 所以在旋转以后它们会在整个坐标轴的两端
• 那么可以把末尾的相等的数全部删掉,删掉后就和无重复的旋转数组一样了

时间复杂度(O(logn))

class Solution {
    public int findMin(int[] nums) {
        int n = nums.length;
        while(n != 0 && nums[n-1] == nums[0])
            n--;
        if(n == 0)
            return nums[0];
        int l = 0;
        int r = n-1;
        while(l < r){
            int mid = l + r >> 1;
            if(nums[mid] <= nums[n-1])
                r = mid;
            else
                l = mid + 1;
        }
        return nums[r];
    }
}