Comment déterminer efficacement si une tranche entière est un sous-ensemble d’une autre dans Go ?

Vérification de sous-ensemble avec des tranches entières dans Go

Déterminer efficacement si une tranche est un sous-ensemble d'une autre est un problème courant en programmation. Sans une approche appropriée, parcourir chaque élément des tranches à des fins de comparaison peut prendre du temps.

Solution optimale : approche basée sur une carte

Une solution efficace à ce problème utilise une structure de données cartographiques. . Voici comment cela fonctionne :

<code class="go">package main

import "fmt"

func subset(first, second []int) bool {
    set := make(map[int]int)
    for _, value := range second {
        set[value] += 1
    }

    for _, value := range first {
        if count, found := set[value]; !found {
            return false
        } else if count < 1 {
            return false
        } else {
            set[value] = count - 1
        }
    }

    return true
}

func main() {
    fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4})) // true
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4})) // false
}</code>

Dans cette approche :

1. Nous créons une carte (ensemble) pour stocker les éléments de la deuxième tranche ainsi que leurs décomptes.
2. Nous parcourons la première tranche et vérifions si chaque élément existe dans la carte. Si un élément n'est pas trouvé, les tranches ne sont pas un sous-ensemble.
3. Si un élément est trouvé, nous décrémentons son nombre dans la carte. Si le nombre devient zéro, nous savons que nous avons rencontré toutes les instances de cet élément.
4. Si toutes les vérifications réussissent, nous renvoyons vrai, indiquant que la première tranche est un sous-ensemble de la seconde.

Gestion des valeurs en double

La solution ci-dessus gère également efficacement les valeurs en double. Par exemple, {1, 2, 2} n'est pas un sous-ensemble de {1, 2, 3, 4} car la deuxième tranche ne contient qu'un seul 2. Les pistes de code comptent dans la carte, garantissant que la première tranche n'a plus de doublons. éléments que la deuxième tranche.

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!