[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);
上一篇: Python爬虫的N种姿势