golang 中計算有序數組交集的高效算法包括：逐個比較（o(mn)），二分搜索（o(m log n) 或 o(n log m)），和使用 map（o(m + n)），其中 m 和 n 是數組的長度。
Golang 中數組交集的高效算法
在 Golang 中計算兩個有序數組的交集是一個常見的任務。有幾種算法可以解決這個問題，從簡單的逐個比較到利用二分搜索和高級數據結構的高效方法。
逐個比較
最簡單的方法是順序比較兩個數組中的每個元素。當找到一個匹配的元素時，將它添加到結果數組中。但是，這種方法的時間復雜度為 O(mn)，其中 m 和 n 是兩個數組的長度。當數組很大時，這種方法會變得非常慢。
func intersect_naive(arr1, arr2 []int) []int {
result := []int{}
for i := 0; i < len(arr1); i++ {
for j := 0; j < len(arr2); j++ {
if arr1[i] == arr2[j] {
result = append(result, arr1[i])
}
}
}
return result
}
登錄后復制
二分搜索
一種更有效的方法是使用二分搜索。對于每個數組中的元素，我們可以使用二分搜索來檢查它是否在另一個數組中。這將導致時間復雜度為 O(m log n) 或 O(n log m)，具體取決于數組的大小。
func intersect_binary_search(arr1, arr2 []int) []int {
result := []int{}
for _, v := range arr1 {
if exists := binarySearch(arr2, v); exists {
result = append(result, v)
}
}
return result
}
func binarySearch(arr []int, target int) bool {
left, right := 0, len(arr)-1
for left <= right {
mid := left + (right-left)/2
if arr[mid] == target {
return true
} else if arr[mid] < target {
left = mid + 1
} else {
right = mid - 1
}
}
return false
}
登錄后復制
使用 map
使用 map（哈希表）是計算交集的另一種高效方法。我們可以將一個數組中的元素作為鍵存儲在 map 中，并記錄每個元素出現的次數。然后，我們遍歷另一個數組，并檢查每個元素是否在 map 中。如果存在，我們將它添加到結果數組中，并更新計數。這將導致時間復雜度為 O(m + n)，其中 m 和 n 是兩個數組的長度。
func intersect_map(arr1, arr2 []int) []int {
result := []int{}
m := make(map[int]int)
for _, v := range arr1 {
m[v]++
}
for _, v := range arr2 {
if count, ok := m[v]; ok {
result = append(result, v)
count--
if count == 0 {
delete(m, v)
} else {
m[v] = count
}
}
}
return result
}
登錄后復制
實戰案例
以下是一個使用交集算法的實際案例：
arr1 := []int{1, 2, 3, 4, 5}
arr2 := []int{3, 4, 5, 6, 7}
result := intersect_map(arr1, arr2)
fmt.Println(result) // 輸出：[3, 4, 5]
登錄后復制
在這個例子中，intersect_map 函數用于計算兩個有序數組的交集，結果存儲在 result 變量中。
