Go で 1 つの整数スライスが別の整数スライスのサブセットであるかどうかを効率的に判断するにはどうすればよいですか?

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] += 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>

このアプローチでは:

1. 2 番目のスライスの要素をその数とともに保存するマップ (セット) を作成します。
2. 最初のスライスを反復処理して、マップ内に各要素が存在するかどうかを確認します。要素が見つからない場合、スライスはサブセットではありません。
3. 要素が見つかった場合は、マップ内のそのカウントをデクリメントします。カウントがゼロになると、その要素のすべてのインスタンスに遭遇したことがわかります。
4. すべてのチェックに合格すると、true を返し、最初のスライスが 2 番目のスライスのサブセットであることを示します。

重複値の処理

上記のソリューションは、重複値も効果的に処理します。たとえば、2 番目のスライスには 2 が 1 つしか含まれていないため、{1, 2, 2} は {1, 2, 3, 4} のサブセットではありません。コードはマップ内のカウントを追跡し、最初のスライスに重複がないことを確認します。 2 番目のスライスよりも要素が異なります。

以上がGo で 1 つの整数スライスが別の整数スライスのサブセットであるかどうかを効率的に判断するにはどうすればよいですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。