好的，陣列和鏈結串列是資料結構中最基礎且常用的兩種。它們有很多常見的操作。這裡我將針對你提到的兩個範例：反轉鏈結串列 和 尋找陣列中第k大的元素，提供詳細的解釋、程式碼實現（以 PHP 為例）以及它們的複雜度分析。
1. 反轉鏈結串列 (Reversing a Linked List)
什麼是鏈結串列？
鏈結串列 (Linked List) 是一種線性資料結構，它由一系列節點 (Node) 組成。每個節點包含兩個部分：
- 資料 (Data): 儲存節點的實際值。
- 指標 (Pointer/Reference): 指向序列中的下一個節點。
鏈結串列的最後一個節點的指標通常指向
null(或nullptr)，表示串列的結束。
與陣列不同，鏈結串列的元素在記憶體中不一定是連續存放的。
反轉鏈結串列的目標
將一個給定的鏈結串列，使其節點的順序顛倒。例如：
1 -> 2 -> 3 -> 4 -> NULL 反轉後變成 4 -> 3 -> 2 -> 1 -> NULL
反轉鏈結串列的演算法 (迭代法)
迭代法是反轉鏈結串列最常見且效率較高的方法。它使用三個指標來追蹤節點：
$prev: 指向前一個節點 (初始化為NULL)$curr: 指向當前處理的節點 (初始化為串列的頭節點head)$next: 暫存下一個節點，以防止在修改$curr的next指標後失去對後續節點的引用。
步驟：
- 初始化
$prev = NULL。 - 初始化
$curr = head。 - 當
$curr不為NULL時，重複以下操作： a. 將$next暫存為$curr->next(保存下一個節點的引用)。 b. 將$curr->next指向$prev(反轉當前節點的指向)。 c. 將$prev更新為$curr(將當前節點設為下一次迭代的前一個節點)。 d. 將$curr更新為$next(移動到下一個節點)。 - 迴圈結束後，
$prev將指向新的頭節點。
PHP 程式碼實現
首先定義一個鏈結串列的節點類別：
PHP
class ListNode {
public $val;
public $next;
function __construct($val = 0, $next = null) {
$this->val = $val;
$this->next = $next;
}
}
class LinkedListReverser {
/**
* 反轉鏈結串列
*
* @param ListNode $head 鏈結串列的頭節點
* @return ListNode 反轉後的新頭節點
*/
public function reverseList(?ListNode $head): ?ListNode {
$prev = null;
$curr = $head;
while ($curr !== null) {
$nextTemp = $curr->next; // 1. 暫存下一個節點
$curr->next = $prev; // 2. 反轉當前節點的 next 指標
$prev = $curr; // 3. 移動 prev 到當前節點
$curr = $nextTemp; // 4. 移動 curr 到下一個節點
}
return $prev; // prev 現在是新的頭節點
}
// 輔助函數：從陣列創建鏈結串列
public function createLinkedList(array $arr): ?ListNode {
if (empty($arr)) {
return null;
}
$head = new ListNode($arr[0]);
$current = $head;
for ($i = 1; $i < count($arr); $i++) {
$current->next = new ListNode($arr[$i]);
$current = $current->next;
}
return $head;
}
// 輔助函數：列印鏈結串列
public function printLinkedList(?ListNode $head): void {
$current = $head;
$elements = [];
while ($current !== null) {
$elements[] = $current->val;
$current = $current->next;
}
echo implode(" -> ", $elements) . " -> NULL\n";
}
}
// --- 測試 ---
$reverser = new LinkedListReverser();
// 創建鏈結串列: 1 -> 2 -> 3 -> 4 -> NULL
$head = $reverser->createLinkedList([1, 2, 3, 4]);
echo "原始鏈結串列: ";
$reverser->printLinkedList($head);
// 反轉鏈結串列
$reversedHead = $reverser->reverseList($head);
echo "反轉後鏈結串列: ";
$reverser->printLinkedList($reversedHead);
// 測試空鏈結串列
$emptyHead = $reverser->createLinkedList([]);
echo "原始空鏈結串列: ";
$reverser->printLinkedList($emptyHead);
$reversedEmptyHead = $reverser->reverseList($emptyHead);
echo "反轉後空鏈結串列: ";
$reverser->printLinkedList($reversedEmptyHead);
// 測試單一節點鏈結串列
$singleNodeHead = $reverser->createLinkedList([5]);
echo "原始單一節點鏈結串列: ";
$reverser->printLinkedList($singleNodeHead);
$reversedSingleNodeHead = $reverser->reverseList($singleNodeHead);
echo "反轉後單一節點鏈結串列: ";
$reverser->printLinkedList($reversedSingleNodeHead);
複雜度分析
- 時間複雜度： O(N)
- 我們只對鏈結串列進行了一次遍歷，每個節點只處理一次。N 是鏈結串列中節點的數量。
- 空間複雜度： O(1)
- 我們只使用了幾個固定的指標變數 (
$prev,$curr,$nextTemp)，沒有額外使用與輸入大小相關的記憶體空間。
- 我們只使用了幾個固定的指標變數 (
2. 尋找陣列中第k大的元素 (Finding the Kth Largest Element in an Array)
目標
給定一個未排序的陣列和一個整數 k，找到陣列中第 k 大的元素。
請注意，這是指在排序後的陣列中第 k 個元素，而不是第 k 個不同的元素。
範例：
陣列：[3, 2, 1, 5, 6, 4], k=2
排序後：[1, 2, 3, 4, 5, 6]
第 2 大的元素是 5。
常用方法與演算法
-
排序法 (Sorting): 最直觀的方法是將整個陣列排序，然後直接取出第 個元素 (如果從小到大排序) 或第 個元素 (如果從大到小排序)。
- 時間複雜度： 取決於排序演算法。一般基於比較的排序演算法是 O(NlogN)。
- 空間複雜度： 取決於排序演算法，可能是 O(1) 或 O(N)。
-
堆積法 (Heap / Priority Queue):
- 使用最小堆 (Min-Heap) 來維護 k 個最大的元素。遍歷陣列，如果當前元素大於堆頂元素，則將堆頂元素移除並將當前元素加入堆。
- 時間複雜度： O(Nlogk)。
- 空間複雜度： O(k) (用於儲存堆)。
-
快速選擇法 (Quickselect / Partition-based Selection):
- 這是基於快速排序 (Quicksort) 思想的演算法，但只對包含目標元素的子陣列進行遞迴。平均情況下比排序法更快。
- 時間複雜度： 平均 O(N)，最差 O(N2) (如果 pivot 選擇不當，但可透過隨機化 pivot 避免)。
- 空間複雜度： O(logN) (遞迴堆疊深度) 或 O(1) (尾遞迴最佳化)。
這裡我們主要示範排序法和堆積法，因為它們更常用於教學和理解。
PHP 程式碼實現
方法一：排序法
PHP
class KthLargestElementFinder {
/**
* 使用排序法尋找陣列中第k大的元素
* 時間複雜度: O(N log N)
* 空間複雜度: O(1) (in-place sort) 或 O(N) (copy for sort)
*
* @param array $nums 輸入陣列
* @param int $k 第k大
* @return int 第k大的元素
* @throws InvalidArgumentException 如果k超出範圍
*/
public function findKthLargestUsingSort(array $nums, int $k): int {
if ($k <= 0 || $k > count($nums)) {
throw new InvalidArgumentException("k 必須在 1 到陣列長度之間。");
}
// 使用 rsort 從大到小排序
rsort($nums);
// 第k大的元素在排序後的陣列中就是索引 k-1 的位置
return $nums[$k - 1];
}
// --- 測試 ---
public static function testSortMethod(): void {
$finder = new KthLargestElementFinder();
$arr1 = [3, 2, 1, 5, 6, 4];
$k1 = 2;
echo "陣列: [" . implode(", ", $arr1) . "], k = {$k1}\n";
echo "第{$k1}大元素 (排序法): " . $finder->findKthLargestUsingSort($arr1, $k1) . "\n\n"; // 預期輸出: 5
$arr2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
$k2 = 4;
echo "陣列: [" . implode(", ", $arr2) . "], k = {$k2}\n";
echo "第{$k2}大元素 (排序法): " . $finder->findKthLargestUsingSort($arr2, $k2) . "\n\n"; // 預期輸出: 4
try {
$finder->findKthLargestUsingSort([1, 2], 3);
} catch (InvalidArgumentException $e) {
echo "錯誤: " . $e->getMessage() . "\n\n";
}
}
}
// 執行測試
KthLargestElementFinder::testSortMethod();
方法二：堆積法 (使用 PHP 的 SplMinHeap)
PHP 的 SplMinHeap 是一個內建的最小堆 (Min-Heap) 實現。
PHP
// 假設 KthLargestElementFinder 類別已定義
/**
* SplMinHeap 的擴展，用於處理 Kth largest
*/
class MinHeapForKthLargest extends SplMinHeap {
// 預設行為已經是最小堆，符合需求
}
class KthLargestElementFinder {
/**
* 使用最小堆尋找陣列中第k大的元素
* 時間複雜度: O(N log k)
* 空間複雜度: O(k)
*
* @param array $nums 輸入陣列
* @param int $k 第k大
* @return int 第k大的元素
* @throws InvalidArgumentException 如果k超出範圍
*/
public function findKthLargestUsingHeap(array $nums, int $k): int {
if ($k <= 0 || $k > count($nums)) {
throw new InvalidArgumentException("k 必須在 1 到陣列長度之間。");
}
$minHeap = new MinHeapForKthLargest();
foreach ($nums as $num) {
$minHeap->insert($num); // 插入元素到最小堆
// 如果堆的大小超過 k，則移除堆頂 (最小的元素)
if ($minHeap->count() > $k) {
$minHeap->extract();
}
}
// 堆中剩下的 k 個元素中，堆頂就是第 k 大的元素
return $minHeap->top();
}
// --- 測試 ---
public static function testHeapMethod(): void {
$finder = new KthLargestElementFinder();
$arr1 = [3, 2, 1, 5, 6, 4];
$k1 = 2;
echo "陣列: [" . implode(", ", $arr1) . "], k = {$k1}\n";
echo "第{$k1}大元素 (堆積法): " . $finder->findKthLargestUsingHeap($arr1, $k1) . "\n\n"; // 預期輸出: 5
$arr2 = [3, 2, 3, 1, 2, 4, 5, 5, 6];
$k2 = 4;
echo "陣列: [" . implode(", ", $arr2) . "], k = {$k2}\n";
echo "第{$k2}大元素 (堆積法): " . $finder->findKthLargestUsingHeap($arr2, $k2) . "\n\n"; // 預期輸出: 4
try {
$finder->findKthLargestUsingHeap([1, 2], 3);
} catch (InvalidArgumentException $e) {
echo "錯誤: " . $e->getMessage() . "\n\n";
}
}
}
// 執行測試
KthLargestElementFinder::testHeapMethod();
快速選擇法 (Quickselect) - 簡要說明
雖然複雜度最低，但實現起來稍微複雜。其基本思想是：
- 選擇一個支點 (pivot)。
- 分割 (partition) 陣列： 將陣列重新排列，使得所有小於 pivot 的元素都在左側，所有大於 pivot 的元素都在右側，pivot 位於中間的正確位置。
- 判斷位置：
- 如果 pivot 的位置就是第 k 大元素的位置，則找到。
- 如果 pivot 的位置在第 k 大元素之前，則在右側子陣列中遞迴尋找。
- 如果 pivot 的位置在第 k 大元素之後，則在左側子陣列中遞迴尋找。 平均時間複雜度為 O(N)，這對於大型數據集來說非常高效。
希望這些解釋和範例能幫助你更好地理解鏈結串列和陣列的這些常見操作！
沒有留言:
張貼留言