好的，我們來實作兩個常見的演算法題目：
- 實作一個簡單的排序演算法：快速排序 (Quick Sort)
- 解決一個特定問題：兩數之和 (Two Sum)
1. 實作快速排序 (Quick Sort)
演算法概述
快速排序 (Quick Sort) 是一種高效的分治法 (Divide and Conquer) 排序演算法。它的基本思想是：
- 選擇基準 (Pivot Selection): 從陣列中選擇一個元素作為「基準」(pivot)。
- 分割 (Partition): 將陣列重新排列，使得所有小於基準的元素都移到基準的左邊，所有大於基準的元素都移到基準的右邊。經過分割之後，基準就位於其最終的排序位置上。
- 遞迴排序： 遞迴地對基準左右兩邊的子陣列重複上述步驟，直到所有子陣列都只包含一個元素或為空。
優點：
- 平均時間複雜度 ：在大多數情況下，它的性能非常優異。
- 原地排序 (In-place sorting)：它通常只需要 O(logN) 的額外空間用於遞迴堆疊，或 O(1) 的額外空間如果使用尾遞迴最佳化。
缺點：
- 最差時間複雜度 ：如果基準選擇不當 (例如，每次都選擇最大或最小元素)，會退化到 O(N2)。這可以透過隨機選擇基準或使用三中位數法來避免。
- 不穩定排序：相等元素的相對順序在排序後可能會改變。
PHP 程式碼實現
我們將實現一個典型的快速排序，使用 Lomuto 分割方案 (Hoare 分割方案通常更優，但 Lomuto 較易理解)。
PHP
class QuickSort {
/**
* 快速排序主函數
*
* @param array $arr 要排序的陣列
* @return array 排序後的陣列
*/
public function sort(array $arr): array {
// 為了避免直接修改原陣列，複製一份
$n = count($arr);
if ($n <= 1) {
return $arr; // 陣列為空或只有一個元素時，已經是排序狀態
}
$this->quickSortRecursive($arr, 0, $n - 1);
return $arr;
}
/**
* 遞迴實現快速排序
*
* @param array $arr 陣列引用
* @param int $low 當前子陣列的起始索引
* @param int $high 當前子陣列的結束索引
*/
private function quickSortRecursive(array &$arr, int $low, int $high): void {
if ($low < $high) {
// 找到基準元素的位置
$pivotIndex = $this->partition($arr, $low, $high);
// 遞迴地對左右兩邊的子陣列進行排序
$this->quickSortRecursive($arr, $low, $pivotIndex - 1);
$this->quickSortRecursive($arr, $pivotIndex + 1, $high);
}
}
/**
* 分割函數 (Lomuto Partition Scheme)
* 將陣列分割成小於基準、基準、大於基準三部分
*
* @param array $arr 陣列引用
* @param int $low 當前子陣列的起始索引
* @param int $high 當前子陣列的結束索引
* @return int 基準元素最終的索引位置
*/
private function partition(array &$arr, int $low, int $high): int {
// 選擇最後一個元素作為基準
$pivot = $arr[$high];
$i = $low - 1; // i 是小於基準的元素的尾部索引
for ($j = $low; $j < $high; $j++) {
// 如果當前元素小於或等於基準
if ($arr[$j] <= $pivot) {
$i++;
// 交換 arr[$i] 和 arr[$j]
$this->swap($arr, $i, $j);
}
}
// 將基準元素放到正確的位置 (i+1)
$this->swap($arr, $i + 1, $high);
return $i + 1; // 返回基準元素的位置
}
/**
* 輔助函數：交換陣列中兩個元素的位置
*
* @param array $arr 陣列引用
* @param int $idx1 索引1
* @param int $idx2 索引2
*/
private function swap(array &$arr, int $idx1, int $idx2): void {
$temp = $arr[$idx1];
$arr[$idx1] = $arr[$idx2];
$arr[$idx2] = $temp;
}
}
// --- 測試快速排序 ---
$quickSorter = new QuickSort();
$testArray1 = [5, 2, 9, 1, 7, 6, 3, 8, 4];
echo "原始陣列 1: " . implode(", ", $testArray1) . "\n";
$sortedArray1 = $quickSorter->sort($testArray1);
echo "排序後陣列 1: " . implode(", ", $sortedArray1) . "\n\n"; // 預期: 1, 2, 3, 4, 5, 6, 7, 8, 9
$testArray2 = [10, -1, 0, 5, 20];
echo "原始陣列 2: " . implode(", ", $testArray2) . "\n";
$sortedArray2 = $quickSorter->sort($testArray2);
echo "排序後陣列 2: " . implode(", ", $sortedArray2) . "\n\n"; // 預期: -1, 0, 5, 10, 20
$testArray3 = [3, 3, 3, 3];
echo "原始陣列 3: " . implode(", ", $testArray3) . "\n";
$sortedArray3 = $quickSorter->sort($testArray3);
echo "排序後陣列 3: " . implode(", ", $sortedArray3) . "\n\n"; // 預期: 3, 3, 3, 3
$testArray4 = [];
echo "原始陣列 4: " . implode(", ", $testArray4) . "\n";
$sortedArray4 = $quickSorter->sort($testArray4);
echo "排序後陣列 4: " . implode(", ", $sortedArray4) . "\n\n"; // 預期: (空)
$testArray5 = [7];
echo "原始陣列 5: " . implode(", ", $testArray5) . "\n";
$sortedArray5 = $quickSorter->sort($testArray5);
echo "排序後陣列 5: " . implode(", ", $sortedArray5) . "\n\n"; // 預期: 7
2. 兩數之和 (Two Sum)
問題描述
給定一個整數陣列 nums 和一個目標值 target。請你在該陣列中找出兩個數，它們的和等於 target，並返回它們在陣列中的索引。
你可以假設每個輸入都只有一個解決方案，並且你不能重複使用相同的元素。
範例：
nums = [2, 7, 11, 15],target = 9- 因為
nums[0] + nums[1] = 2 + 7 = 9，所以返回[0, 1]。
解決方案思路
最直觀的方法是使用嵌套迴圈，遍歷所有可能的兩數組合，檢查它們的和是否等於 target。
- 時間複雜度：，因為需要兩層迴圈。
- 空間複雜度：。
然而，這個問題有一個更高效的解決方案，使用哈希表 (Hash Map / Associative Array)。
使用哈希表的方法：
- 初始化一個空的哈希表 (在 PHP 中就是普通的關聯陣列)。
- 遍歷
nums陣列中的每個數字num和其索引i： a. 計算complement(互補數)：complement = target - num。 b. 檢查哈希表中是否已經存在complement。 * 如果存在，表示我們找到了兩個數：complement（其索引儲存在哈希表中）和當前的num（其索引是i）。返回它們的索引即可。 * 如果不存在，將當前數字num及其索引i存入哈希表。這樣，如果未來的某個數字的complement是當前的num，我們就能快速找到它。 - 如果遍歷完所有數字都沒有找到，則表示沒有解（根據題目假設，這個情況不會發生）。
- 時間複雜度：。因為我們只需要遍歷陣列一次，而哈希表的查找和插入操作的平均時間複雜度為 O(1)。
- 空間複雜度：。在最壞情況下，哈希表可能需要儲存所有 N 個數字。
PHP 程式碼實現
PHP
class TwoSumSolver {
/**
* 尋找兩數之和等於目標值的索引 (使用哈希表)
*
* @param array $nums 輸入的整數陣列
* @param int $target 目標和
* @return array 包含兩個索引的陣列
* @throws Exception 如果沒有找到解 (根據題目假設不會發生，但良好習慣)
*/
public function twoSum(array $nums, int $target): array {
$map = []; // 用於儲存 (數值 => 索引) 的哈希表
foreach ($nums as $index => $num) {
$complement = $target - $num;
// 檢查哈希表中是否已經存在 complement
// array_key_exists 比 isset 更適合檢查值是否為 null
if (array_key_exists($complement, $map)) {
// 如果存在，返回 complement 的索引和當前 num 的索引
return [$map[$complement], $index];
}
// 如果不存在，將當前數字和其索引存入哈希表
$map[$num] = $index;
}
// 根據題目假設，永遠會有一個解，所以這行應該不會被觸發
throw new Exception("沒有找到兩數之和等於目標值的組合。");
}
/**
* 尋找兩數之和等於目標值的索引 (暴力法，僅供比較)
* 時間複雜度: O(N^2)
*/
public function twoSumBruteForce(array $nums, int $target): array {
$n = count($nums);
for ($i = 0; $i < $n; $i++) {
for ($j = $i + 1; $j < $n; $j++) { // 注意 j 從 i+1 開始，避免重複使用同一元素
if ($nums[$i] + $nums[$j] === $target) {
return [$i, $j];
}
}
}
throw new Exception("沒有找到兩數之和等於目標值的組合。");
}
}
// --- 測試兩數之和 ---
$solver = new TwoSumSolver();
$nums1 = [2, 7, 11, 15];
$target1 = 9;
echo "陣列: [" . implode(", ", $nums1) . "], 目標: {$target1}\n";
$result1 = $solver->twoSum($nums1, $target1);
echo "結果 (哈希表): [" . implode(", ", $result1) . "]\n"; // 預期: [0, 1]
$result1_bf = $solver->twoSumBruteForce($nums1, $target1);
echo "結果 (暴力法): [" . implode(", ", $result1_bf) . "]\n\n"; // 預期: [0, 1]
$nums2 = [3, 2, 4];
$target2 = 6;
echo "陣列: [" . implode(", ", $nums2) . "], 目標: {$target2}\n";
$result2 = $solver->twoSum($nums2, $target2);
echo "結果 (哈希表): [" . implode(", ", $result2) . "]\n"; // 預期: [1, 2]
$result2_bf = $solver->twoSumBruteForce($nums2, $target2);
echo "結果 (暴力法): [" . implode(", ", $result2_bf) . "]\n\n"; // 預期: [1, 2]
$nums3 = [3, 3];
$target3 = 6;
echo "陣列: [" . implode(", ", $nums3) . "], 目標: {$target3}\n";
$result3 = $solver->twoSum($nums3, $target3);
echo "結果 (哈希表): [" . implode(", ", $result3) . "]\n"; // 預期: [0, 1]
$result3_bf = $solver->twoSumBruteForce($nums3, $target3);
echo "結果 (暴力法): [" . implode(", ", $result3_bf) . "]\n\n"; // 預期: [0, 1]
這兩個範例展示了常見的演算法問題以及如何使用 PHP 實現它們，同時考慮了時間和空間複雜度。
沒有留言:
張貼留言