Maison > développement back-end > Golang > le corps du texte

Algorithme efficace pour l'intersection de tableaux dans Golang

WBOY
Libérer: 2024-04-04 11:36:01
original
565 Les gens l'ont consulté

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.

Golang 中数组交集的高效算法

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
}
Copier après la connexion

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
}
Copier après la connexion

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
}
Copier après la connexion

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]
Copier après la connexion

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!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal
À propos de nous Clause de non-responsabilité Sitemap
Site Web PHP chinois:Formation PHP en ligne sur le bien-être public,Aidez les apprenants PHP à grandir rapidement!