欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[PHP]算法-旋转数组的最小值的PHP实现

程序员文章站 2022-03-26 09:33:44
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。 1.可以看成是二分查找... ......
把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 note:给出的所有元素都大于0,若数组大小为0,请返回0。

1.可以看成是二分查找法,查找最小的元素
2.{3,4,5,1,2} 可以看成{3,4,5} {1,2},left和right两个指针分别指向第一个和最后一个
3.mid=left+(right-left)/2 如果arr[left] <= arr[mid]  那么 left指针移到mid处,left=mid
    如果arr[left] > arr[mid]那中间元素必定是在右半区,right指针移到mid处  right=mid
4.终止条件是right-left=1 mid=right
5.

minnumberinrotatearray(arr)
    while arr[left]>arr[right]
        if (right-left)==1
            mid=right
            break
        mid=left+(right-left)/2
        if arr[left]<=arr[mid]
            left=mid
        else
            right=mid
    return arr[mid]

 

 

function minnumberinrotatearray($arr)
{
        $left=0;
        $size=count($arr);
        $right=$size-1;
        $mid=$left+intval(($right-$left)/2);
        while($arr[$left]>=$arr[$right]){
                if(($right-$left)==1){
                        $mid=$right;
                        break;
                }   
                $mid=$left+intval(($right-$left)/2);
                if($arr[$left]<=$arr[$mid]){
                        $left=$mid;
                }else{
                        $right=$mid;
                }   
        }   
        return $arr[$mid];
}

$arr=array(3,4,5,1,2);
$m=minnumberinrotatearray($arr);
var_dump($m);