Maison >développement back-end >Golang >Comment vérifier efficacement les sous-ensembles avec des tranches entières dans Go ?

Comment vérifier efficacement les sous-ensembles avec des tranches entières dans Go ?

Barbara Streisand
Barbara Streisandoriginal
2024-10-27 05:03:03869parcourir

How to Efficiently Check for Subsets with Integer Slices in Go?

Vérification efficace des sous-ensembles avec des tranches entières dans Go

Déterminer si une tranche est un sous-ensemble d'une autre est une tâche de programmation courante. Bien que parcourir les tranches soit une approche simple, il vaut la peine d'explorer des méthodes plus efficaces.

Une solution efficace consiste à utiliser une structure de données cartographiques. Cette technique crée une carte avec les éléments de la plus grande tranche comme clés et leurs fréquences respectives comme valeurs. Ensuite, les éléments de la plus petite tranche sont comparés à la carte. Si tous les éléments sont trouvés dans la carte avec des fréquences suffisantes, la plus petite tranche est considérée comme un sous-ensemble de la plus grande.

Un exemple d'implémentation dans Go :

<code class="go">package main

import "fmt"

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

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

    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>

Cette approche vérifie efficacement sous-ensembles en un temps O(n), où n est la longueur de la plus grande tranche. Il gère efficacement les valeurs en double, ce qui est une exigence courante dans de tels scénarios.

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!

Déclaration:
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