当前位置:首页 > PHP教程 > php数组 > 列表

php实现有序数组旋转后寻找最小值方法

发布:smiling 来源: PHP粉丝网  添加日期:2021-10-30 11:44:37 浏览: 评论:0 

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转,输出旋转数组的最小元素,例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。

NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

1、利用二分法寻找数组中的最小元素

2、定义两个 指针left和right,指向数组的第一个元素和最后一个元素,定义一个中间指针mid

3、如果arr[left]小于arr[mid],那么把左边指针移动到mid处,mid从新计算 4.如果arr[left]大于arr[mid],那么把右边指针移动到mid处,mid从新计算,缩小范围

  1. left=0 right=arr.length-1 
  2. while arr[left]>=arr[right] 
  3.   if right-left==1 
  4.     mid=right 
  5.     break 
  6.   mid=left+(right-left)/2 
  7.   if arr[left]<=arr[mid] 
  8.     left=mid 
  9.   else 
  10.     right=mid 
  11. return arr[mid] 
  12.  
  13. <?php 
  14. $arr=array(3,4,5,6,1,2); 
  15. function minNumberInRotateArray($rotateArray){ 
  16.     $left=0;//左边指针 
  17.     $right=count($rotateArray)-1;//右边指针 
  18.     //判断条件,left大于right就一直进行 
  19.     while($rotateArray[$left]>=$rotateArray[$right]){ 
  20.         //left和right已经紧挨着了 
  21.         if(($right-$left)==1){ 
  22.             $mid=$right
  23.             break
  24.         }   
  25.         //中间点 
  26.         $mid=ceil($left+($right-$left)/2); 
  27.         //left小于中间点 
  28.         if($rotateArray[$left]<$rotateArray[$mid]){ 
  29.             //left移动到中间点 
  30.             $left=$mid
  31.         }else
  32.             //right移动到中间点 
  33.             $right=$mid
  34.         }   
  35.     }   
  36.      
  37.     return $rotateArray[$mid]; 
  38. $min=minNumberInRotateArray($arr); 
  39. var_dump($min);//int(1)

Tags: php有序数组 php寻找最小值

分享到: