PHP如何旋转数组并求最小数

在编程中，数组操作是非常常见的任务之一。PHP作为一种广泛使用的服务器端脚本语言，提供了丰富的数组操作函数。本文将介绍如何在PHP中旋转数组，并找到旋转后的数组中的最小数。

什么是旋转数组？

旋转数组是指将一个有序数组的前若干个元素移动到数组的末尾。例如，数组 [1, 2, 3, 4, 5] 旋转一次后变为 [2, 3, 4, 5, 1]，旋转两次后变为 [3, 4, 5, 1, 2]，以此类推。

旋转数组的实现

在PHP中，我们可以使用多种方法来旋转数组。以下是两种常见的方法：

方法一：使用 array_slice 和 array_merge

array_slice 函数可以用于从数组中提取一部分元素，而 array_merge 函数可以将多个数组合并成一个数组。通过结合这两个函数，我们可以轻松地实现数组的旋转。

function rotateArray($arr, $k) {
    $n = count($arr);
    $k = $k % $n; // 处理旋转次数大于数组长度的情况
    return array_merge(array_slice($arr, $k), array_slice($arr, 0, $k));
}

$arr = [1, 2, 3, 4, 5];
$k = 2;
$rotatedArr = rotateArray($arr, $k);
print_r($rotatedArr); // 输出: [3, 4, 5, 1, 2]

方法二：使用循环和 array_shift

array_shift 函数可以移除数组的第一个元素并返回该元素。我们可以通过循环调用 array_shift 来实现数组的旋转。

function rotateArray($arr, $k) {
    for ($i = 0; $i < $k; $i++) {
        $firstElement = array_shift($arr);
        array_push($arr, $firstElement);
    }
    return $arr;
}

$arr = [1, 2, 3, 4, 5];
$k = 2;
$rotatedArr = rotateArray($arr, $k);
print_r($rotatedArr); // 输出: [3, 4, 5, 1, 2]

寻找旋转数组中的最小数

旋转后的数组仍然是有序的，只是起点发生了变化。因此，我们可以利用二分查找算法来高效地找到最小数。

二分查找算法

二分查找是一种在有序数组中查找特定元素的高效算法。在旋转数组中，我们可以通过比较中间元素与左右边界元素来确定最小数的位置。

function findMin($arr) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left < $right) {
        $mid = intval(($left + $right) / 2);

        if ($arr[$mid] > $arr[$right]) {
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }

    return $arr[$left];
}

$arr = [3, 4, 5, 1, 2];
$min = findMin($arr);
echo $min; // 输出: 1

解释

1. 初始化指针：我们初始化两个指针 $left 和 $right，分别指向数组的起始和末尾。
2. 循环查找：在循环中，我们计算中间位置 $mid，并比较 $arr[$mid] 和 $arr[$right]。
   • 如果 $arr[$mid] 大于 $arr[$right]，说明最小数在右半部分，我们将 $left 移动到 $mid + 1。
   • 否则，最小数在左半部分或就是 $mid，我们将 $right 移动到 $mid。
3. 返回结果：当 $left 和 $right 相遇时，$arr[$left] 就是最小数。

完整示例

以下是一个完整的示例，展示了如何旋转数组并找到最小数：

function rotateArray($arr, $k) {
    $n = count($arr);
    $k = $k % $n;
    return array_merge(array_slice($arr, $k), array_slice($arr, 0, $k));
}

function findMin($arr) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left < $right) {
        $mid = intval(($left + $right) / 2);

        if ($arr[$mid] > $arr[$right]) {
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }

    return $arr[$left];
}

$arr = [1, 2, 3, 4, 5];
$k = 2;
$rotatedArr = rotateArray($arr, $k);
$min = findMin($rotatedArr);

echo "旋转后的数组: ";
print_r($rotatedArr);
echo "最小数: " . $min;

输出

旋转后的数组: Array
(
    [0] => 3
    [1] => 4
    [2] => 5
    [3] => 1
    [4] => 2
)
最小数: 1

总结

在PHP中，旋转数组并找到最小数是一个常见的编程任务。通过使用 array_slice 和 array_merge 函数，我们可以轻松地实现数组的旋转。而通过二分查找算法，我们可以高效地找到旋转数组中的最小数。希望本文的介绍能够帮助你更好地理解和掌握这些技巧。