剑指Offer - PHP旋转数组的最小数字
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
分析
升序旋转数组的特点
- 数组可以看成两个子升序数组，
数组 A和数组 B - 我们要找的数为
数组 B的第一个数
解法一：循环数组
循环数组，找出最小值。时间复杂度O(N)。
解法二：min()函数
php 的min()函数直接找到。
解法三：二分查找法
binary_search()代码说明：$mid = intval($low + ($high-$low)/2);：这样写是为了防止溢出。$arr[$mid] > $arr[$low]：如果中间值 > 左边值，说明中间值在左边的递增子数组，最小值应该在中间值的右边。$arr[$mid] < $arr[$high]：如果中间值 < 右边值，说明中间值在右边的递增子数组，最小值应该在中间值的左边。$low++：如果有重复数字比较不出大小，则 $low 往右移一位
/**
* 时间复杂度 O(logN)
*/
public function rotateArray()
{
$rotateArr = [3,4,5,1,2]; // [2,2,2,0,1] 这是有重复数字的数组
$low = 0; // 数组最左边
$high = count($rotateArr)-1; // 数组最右边
$index = $this->binary_search($low, $high, $rotateArr); // 调用二分查找的函数
return $index; // 返回数组最小值的下标
}
/**
* 二分查找的函数
*/
public function binary_search($low, $high, $arr)
{
while ($low < $high) {
$mid = intval($low + ($high-$low)/2); // 取中间值，整型。
if ($high - $low == 1) return $high; // 如果剩最后两个，取右边。
if ($arr[$mid] > $arr[$low]) $low = $mid; // 最小值应该在中间值的右边
elseif ($arr[$mid] < $arr[$high]) $high = $mid; // 最小值应该在中间值的左边
else $low++; // $low 往右移一位
}
return $high;
}
关于 LearnKu
粤公网安备 44030502004330号