php如何旋轉數組并求最小數

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 函數，我們可以輕松地實現數組的旋轉。而通過二分查找算法，我們可以高效地找到旋轉數組中的最小數。希望本文的介紹能夠幫助你更好地理解和掌握這些技巧。