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

╰半橙微兮° 2024-04-01 11:08 98阅读 0赞

问题描述：

> 已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = \[0,1,4,4,5,6,7\] 在变化后可能得到：  
> 若旋转 4 次，则可以得到 \[4,5,6,7,0,1,4\]  
> 若旋转 7 次，则可以得到 \[0,1,4,4,5,6,7\]  
> 注意，数组 \[a\[0\], a\[1\], a\[2\], …, a\[n-1\]\] 旋转一次 的结果为数组 \[a\[n-1\], a\[0\], a\[1\], a\[2\], …, a\[n-2\]\] 。  
> 给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。  
> 你必须尽可能减少整个过程的操作步骤。

这题可以参考[153. 寻找旋转排序数组中的最小值][153.]  
但是不同的是这题的数组中包含了重复值。

算法思路：同样的思路，找到最小值，即和最后一位数字比较，大于为0，小于为1，找到第一个小于等于的数字。  
因为可能是重复值，比如\[3,1,3\]，这个时候你会发现，大于等于为0，还是小于等于为1，都是\[0,1,0\] 或者\[1,0,1\]，并不满足单调条件。

之前的二分查找都是三步走，写好条件，然后看是否包含mid，然后再写else。

现在多了个重复值，“=”的时候很难解决。  
换个思路，那能不能给等于的时候单独处理一下。

如果mid=right,那说明right这一位肯定不是最小值，即使是最小值，也会取mid,而不是right。所以mid其实是right完美的替代者。  
只通过mid=right，也无法判断要取左边还是右边.  
比如 \[3,1,3,3\]。但是我们能肯定的是，right肯定是可以被替代的，那就当mid=right的时候，right–，是肯定满足的。

class Solution {
        
       public int findMin(int[] nums) {
        
            /**
             *  所有元素比最后一个元素比较，大于则为0，小于则为1，就形成了个有序数组,
             *  找到第一个小于最后一个元素的数即可
                num < end 找end的前驱 
              */
            int left = 0;
            int right = nums.length-1;
            
            while (left<right){
        
                int mid = (left+right)/2;
                if(nums[mid]<nums[right]){
        
                    right = mid;
                }else if(nums[mid]>nums[right]){
        
                    left = mid+1;
                }else{
        
                    right--;
                }
            }
            return nums[right];
        }
    }

![在这里插入图片描述][87a4192d564c44879ec31d0483c2910d.png]

[153.]: https://blog.csdn.net/ideaxx/article/details/127523370
[87a4192d564c44879ec31d0483c2910d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/9f657114a1864f379b012e15c5946faa.png