PHP中兩個陣列 [1,2,5,11,32,15,77] 和 [99,32,15,5,1,77]，如何找出共同元素？請撰寫程式碼，並分析時間複雜度（不可使用 array_intersect）。

 給定兩個陣列，目標是找出它們的共同元素，並且不使用 array_intersect 函數。以下將提供兩種方法，分別是使用雜湊表（Hash Map/Set）和排序後雙指針法。

方法一：使用雜湊表 (Hash Map/Set)

這是最有效率的方法之一。我們將第一個陣列的所有元素放入一個雜湊集合中，然後遍歷第二個陣列，檢查每個元素是否存在於雜湊集合中。

程式碼：

Python

def find_common_elements_hash_set(arr1, arr2):
    """
    使用雜湊集合找出兩個陣列的共同元素。

    Args:
        arr1: 第一個陣列。
        arr2: 第二個陣列。

    Returns:
        一個包含共同元素的列表。
    """
    set1 = set(arr1)  # 將第一個陣列轉換為集合
    common_elements = []

    for element in arr2:
        if element in set1:
            common_elements.append(element)
            set1.remove(element)  # 如果元素已找到，從集合中移除以避免重複添加（如果允許重複共同元素則不移除）

    return common_elements

# 範例使用
arr1 = [1, 2, 5, 11, 32, 15, 77]
arr2 = [99, 32, 15, 5, 1, 77]
common = find_common_elements_hash_set(arr1, arr2)
print(f"共同元素 (雜湊集合): {common}")

時間複雜度分析：

1. 建立 set1： 將 arr1 中的所有元素添加到雜湊集合中。平均情況下，每個元素的插入操作是 O(1)。如果 arr1 的長度是 N，那麼這一部分的複雜度是 O(N)。
2. 遍歷 arr2： 遍歷 arr2 中的每個元素。假設 arr2 的長度是 M。
   • element in set1：雜湊集合的查找操作平均情況下是 O(1)。
   • set1.remove(element)：雜湊集合的刪除操作平均情況下是 O(1)。 所以，遍歷 arr2 的複雜度是 O(M)。

綜合來看，使用雜湊表的總時間複雜度是 $O(N+M)$。這是非常高效的，因為它只需要對每個陣列進行一次遍歷（或近似一次）。

方法二：排序後雙指針法

這種方法要求先將兩個陣列排序。然後，使用兩個指針，一個指向第一個陣列的開頭，另一個指向第二個陣列的開頭，逐步比較元素。

程式碼：

Python

def find_common_elements_sorted_pointers(arr1, arr2):
    """
    使用排序和雙指針找出兩個陣列的共同元素。

    Args:
        arr1: 第一個陣列。
        arr2: 第二個陣列。

    Returns:
        一個包含共同元素的列表。
    """
    arr1_sorted = sorted(arr1)  # 排序第一個陣列
    arr2_sorted = sorted(arr2)  # 排序第二個陣列

    common_elements = []
    ptr1 = 0
    ptr2 = 0

    while ptr1 < len(arr1_sorted) and ptr2 < len(arr2_sorted):
        if arr1_sorted[ptr1] == arr2_sorted[ptr2]:
            common_elements.append(arr1_sorted[ptr1])
            ptr1 += 1
            ptr2 += 1
        elif arr1_sorted[ptr1] < arr2_sorted[ptr2]:
            ptr1 += 1
        else: # arr1_sorted[ptr1] > arr2_sorted[ptr2]
            ptr2 += 1

    return common_elements

# 範例使用
arr1 = [1, 2, 5, 11, 32, 15, 77]
arr2 = [99, 32, 15, 5, 1, 77]
common = find_common_elements_sorted_pointers(arr1, arr2)
print(f"共同元素 (排序雙指針): {common}")

時間複雜度分析：

1. 排序：
   • 對 arr1 排序：如果使用標準的比較排序算法（如歸併排序或快速排序），時間複雜度是 O(NlogN)。
   • 對 arr2 排序：時間複雜度是 O(MlogM)。
2. 雙指針遍歷： 兩個指針最多會遍歷兩個陣列的總長度一次。所以這一部分的複雜度是 $O(N+M)$。

綜合來看，排序後雙指針法的總時間複雜度是 $O(N\log N+M\log M)$。

總結與比較

方法	時間複雜度	優點	缺點
雜湊表	$O(N+M)$	最快，對於大規模數據集表現優異	需要額外的空間來儲存雜湊集合 (O(N))
排序雙指針	$O(N\log N+M\log M)$	不需額外的大量空間（如果允許修改原陣列）	比雜湊表慢（當 N,M 很大時）

在大多數情況下，使用雜湊表的方法是更優的選擇，因為它的時間複雜度是線性的。只有當記憶體限制非常嚴格，或者輸入陣列已經排序（或幾乎排序）時，排序雙指針法才可能是一個有競爭力的替代方案。