在Go中使用切片进行子集检查 [英] Subset check with slices in Go

问题描述

我正在寻找一种有效的方法来检查切片是否是另一个切片的子集.我可以简单地遍历它们进行检查，但是我觉得必须有更好的方法.

I am looking for a efficient way to check if a slice is a subset of another. I could simply iterate over them to check, but I feel there has to be a better way.

例如

{1、2、3}是{1、2、3、4}的子集.
{1,2,3}不是{1,2,3,4}的子集

{1, 2, 3} is a subset of {1, 2, 3, 4}
{1, 2, 2} is NOT a subset of {1, 2, 3, 4}

有效执行此操作的最佳方法是什么?

What is the best way to do this efficiently?

谢谢！

推荐答案

我认为解决子集问题的最常见方法是通过地图.

I think the most common way to solve a subset problem is via a map.

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
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}))
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

检查重复值的能力相对罕见.上面的代码按要求解决了问题(请参阅: http://play.golang.org/p/4_7Oh-fgDQ ).如果您打算使用重复的值，则必须像上面的代码一样保留一个计数.如果没有重复的值，则可以通过使用布尔值(而不是整数)来更紧凑地解决问题.

The ability to check duplicate values is relatively uncommon. The code above solves the problem as asked (see: http://play.golang.org/p/4_7Oh-fgDQ) though. If you plan on having duplicate values, you'll have to keep a count like the code above does. If there will not be duplicate values, you can solve the problem more compactly by using a boolean for the map value instead of an integer.

这篇关于在Go中使用切片进行子集检查的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！