LeetCode 154. 寻找旋转排序数组中的最小值 II（元素重复）

痛定思痛。 2022-10-25 04:40 158阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]  
[大佬题解][Link 1].

//解法一:分治
    class Solution {
        
        public int findMin(int[] nums) {
        
            int n = nums.length;
            int l = 0;
            int r = n - 1;
            return bsearch(nums, l, r);
        }
    /*
    发现了一个规律 递增的旋转数组找最小值  mid 只能与 right比较
    */
        private int bsearch(int[] nums, int l, int r){
        
            if(l == r)
                return nums[l];
            if(l + 1 == r)
                return Math.min(nums[l], nums[r]);
            if(nums[l] < nums[r])
                return nums[l];
            int mid = l + r >> 1;
            if(nums[mid] == nums[r]){
        //当中间数与右边界表示的数相等的时候,去掉右边界
                return bsearch(nums, l, r - 1);
            }else if(nums[mid] < nums[r]){
        //当中间数比右边界表示的数小的时候,中间数就可能是目标数.中间数到右边界是递增的（对于这道题是非递减），那么中间数右边的（不包括中间数）就一定不是目标数，可以把它们排除.不过中间数有可能是目标数.把右边界设置为 right = mid
                return bsearch(nums, l, mid);
            }else{
        //当中间数比右边界表示的数大的时候.因此中间数以及中间数前面的数都不是目标数,，把左边界设置中间数位置 + 1，即 left = mid + 1
                return bsearch(nums, mid + 1, r);
            }
        }
    }

//解法二
    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[r]){
        
                    r = mid;
                }else if(nums[mid] > nums[r])
                    l = mid + 1;
                else
                    r--;
            }
            return nums[l];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/95e1380a6fc14ef49470c8c39957c2dc.png
[Link 1]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/er-fen-fa-fen-zhi-fa-python-dai-ma-by-liweiwei1419/