Efficient algorithm for array intersection in Golang

Efficient algorithms for calculating the intersection of ordered arrays in Golang include: comparison one by one (O(mn)), binary search (O(m log n) or O(n log m)), and using map (O(m n) ), where m and n are the lengths of the array.

Efficient Algorithm for Array Intersection in Golang

Computing the intersection of two ordered arrays is a common task in Golang. There are several algorithms for solving this problem, ranging from simple one-by-one comparisons to efficient methods that utilize binary searches and advanced data structures.

Compare one by one

The simplest way is to compare each element in the two arrays sequentially. When a matching element is found, it is added to the resulting array. However, this approach has a time complexity of O(mn), where m and n are the lengths of the two arrays. This approach can become very slow when the array is large.

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
}

Binary Search

A more efficient method is to use binary search. For each element in the array, we can use binary search to check if it is in another array. This results in a time complexity of O(m log n) or O(n log m), depending on the size of the array.

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
}

Use map

Using map (hash table) is another efficient way to calculate intersection. We can store the elements in an array as keys in a map and record the number of times each element appears. Then we iterate through another array and check if each element is in the map. If it exists, we add it to the results array and update the count. This results in a time complexity of O(m n), where m and n are the lengths of the two arrays.

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
}

Practical case

The following is a practical case using the intersection algorithm:

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]

In this example, the intersect_map function is used to calculate two The intersection of ordered arrays, the result is stored in the result variable.

The above is the detailed content of Efficient algorithm for array intersection in Golang. For more information, please follow other related articles on the PHP Chinese website!