萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 判斷陣列是否有序的高效算法實作

問題描述

給定一個數值陣列,判斷其元素是否按「遞增」或「遞減」順序排列。要求時間複雜度 O(n),空間複雜度 O(1),單次遍歷完成判斷。

核心算法邏輯

  1. 先比較前兩個元素確定初始趨勢(遞增/遞減/相等)。
  2. 若前兩元素相等,繼續向後尋找第一組不相等的元素以確定趨勢。
  3. 確立趨勢後,後續元素必須嚴格遵循該趨勢,否則判定為無序。
  4. 全程僅需一個旗標變數記錄趨勢,無需額外空間。

PHP 實作代碼

<?php
/**
 * 判斷陣列是否有序(單調遞增或遞減)
 * @param array $arr 數值陣列
 * @return bool true=有序, false=無序
 */
function isSorted(array $arr): bool {
    $len = count($arr);
    if ($len < 2) return true; // 0或1個元素視為有序

    $trend = 0; // 0=未定, 1=遞增, -1=遞減

    for ($i = 1; $i < $len; $i++) {
        $diff = $arr[$i] - $arr[$i - 1];

        if ($trend === 0) {
            // 尚未確定趨勢
            if ($diff > 0) $trend = 1;
            elseif ($diff < 0) $trend = -1;
            // $diff === 0 繼續循環尋找趨勢
        } else {
            // 已確定趨勢,檢查是否違反
            if ($trend === 1 && $diff < 0) return false; // 應遞增卻變小
            if ($trend === -1 && $diff > 0) return false; // 應遞減卻變大
        }
    }

    return true; // 遍歷完畢無衝突
}

// 測試用例
$tests = [
    [1, 2, 3, 4, 5]         => true,  // 遞增
    [5, 4, 3, 2, 1]         => true,  // 遞減
    [1, 1, 1, 1]            => true,  // 全等視為有序
    [1, 2, 2, 3, 4]         => true,  // 非嚴格遞增
    [1, 3, 2, 4, 5]         => false, // 無序
    [10, 9, 8, 8, 7]        => true,  // 非嚴格遞減
    []                      => true,  // 空陣列
    [42]                    => true,  // 單元素
];

echo "<pre>";
foreach ($tests as $arr => $expected) {
    $result = isSorted($arr);
    $status = $result === $expected ? '✅ PASS' : '❌ FAIL';
    echo "$status | " . json_encode($arr) . " => " . ($result ? '有序' : '無序') . PHP_EOL;
}
echo "</pre>";
?>

代碼優化說明

  • 嚴格模式:若業務要求「嚴格遞增/遞減」(不允許相等元素),只需將 `$diff > 0` 改為 `$diff >= 0` 等邏輯調整即可。
  • 類型安全:PHP 7.1+ 可加入型別宣告 `array $arr: bool`,搭配 `declare(strict_types=1)` 提升可靠度。
  • 擴展性:若需支援自定義比較器(如物件陣列),可增加 `$cmpFn` 參數並使用 `usort` 風格回調。

效能對比

方法時間複雜度空間複雜度備註
本文單次遍歷法O(n)O(1)最優,單趟掃描
排序後比較 sort($arr) === $arrO(n log n)O(n)破壞原陣列,需複製
兩次遍歷分別檢查升/降序O(2n)O(1)常數倍較慢,代碼冗餘

總結

單次遍歷配合趨勢旗標是判斷陣列有序性的標準最優解。本文提供的 `isSorted()` 函數代碼簡潔、邏輯清晰、處理了邊界情況,可直接用於生產環境。理解此算法思路對解決「檢測數據單調性」、「流式數據異常檢測」等問題同樣適用。

copyright © 萬盛學電腦網 all rights reserved