Leetcode刷题之PHP解析( 154. Find Minimum in Rotated Sorted Array II)

 2019-7-18 星期四 开始吧

上一题链接Leetcode基础刷题之PHP解析(153. Find Minimum in Rotated Sorted Array)

题目描述

给定一个不知道在哪个点发生旋转的有序升序数组，求数组中最小值。这题和上一题最大的区别就是有重复值。

题目分析

还是需要通过中间点查找，不同的是每次二分查找如果等于中间数，那么直接把左边的向右边的移动一位，大于或者小于的情况，我们都可以求出这局部的最小值，然后缩小分区，最后进行求左中右三部分的最小值即整体最小值。

代码实现

    /**
     * @param Integer[] $nums
     * @return Integer
     */
    function findMin($nums) {
        $l=0;
        $r=count($nums)-1;
        $res=$nums[0];
        while($l<$r-1){
            $middle=$l+(($r-$l)>>1);
            if($nums[$l]<$nums[$middle]){
                $res=min($nums[$l],$res);
                $l=$middle+1;
            }elseif($nums[$l]>$nums[$middle]){
                $res=min($res,$nums[$r]);
                $r=$middle;
            }else ++$l;
        }
        $res=min($res,$nums[$l],$nums[$r]);
        return $res;
    }

Github整理地址:https://github.com/wuqinqiang/leetcode-php