Algorithme efficace pour l'intersection de tableaux dans Golang

Les algorithmes efficaces pour calculer l'intersection de tableaux ordonnés dans Golang incluent : la comparaison un par un (O(mn)), la recherche binaire (O(m log n) ou O(n log m)) et l'utilisation de la carte (O(m + n) ), où m et n sont les longueurs du tableau.

Algorithme efficace pour l'intersection de tableaux dans Golang

Le calcul de l'intersection de deux tableaux ordonnés est une tâche courante dans Golang. Il existe plusieurs algorithmes pour résoudre ce problème, allant de simples comparaisons une par une à des méthodes efficaces utilisant des recherches binaires et des structures de données avancées.

Comparez un par un

Le moyen le plus simple est de comparer séquentiellement chaque élément des deux tableaux. Lorsqu'un élément correspondant est trouvé, il est ajouté au tableau résultant. Cependant, cette approche a une complexité temporelle de O(mn), où m et n sont les longueurs des deux tableaux. Cette méthode peut devenir très lente lorsque le tableau est grand.

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
}

Recherche binaire

Une méthode plus efficace consiste à utiliser la recherche binaire. Pour chaque élément du tableau, nous pouvons utiliser la recherche binaire pour vérifier s'il se trouve dans un autre tableau. Il en résulte une complexité temporelle de O(m log n) ou O(n log m), selon la taille du tableau.

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
}

Utiliser la carte

L'utilisation de la carte (table de hachage) est un autre moyen efficace de calculer une intersection. Nous pouvons stocker les éléments d'un tableau sous forme de clés dans une carte et enregistrer le nombre de fois où chaque élément apparaît. Ensuite, nous parcourons un autre tableau et vérifions si chaque élément est dans la carte. S'il existe, nous l'ajoutons au tableau des résultats et mettons à jour le décompte. Il en résulte une complexité temporelle de O(m + n), où m et n sont les longueurs des deux tableaux.

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
}

Cas pratique

Ce qui suit est un cas pratique utilisant l'algorithme d'intersection :

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]

Dans cet exemple, intersect_map 函数用于计算两个有序数组的交集，结果存储在 result variables.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!