旋转数组的最小数字

未匹配的标注

题目描述

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [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.com 网站上。

上一篇 下一篇