在Go语言中，使用整数切片进行子集检查。

huangapple
go评论125阅读模式
英文:

Subset check with integer slices in Go

问题

我正在寻找一种高效的方法来检查一个切片是否是另一个切片的子集。我可以简单地迭代它们来进行检查，但我觉得应该有更好的方法。

例如：

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

如何以高效的方式进行这种检查呢？

谢谢！

英文:

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.

E.g.

> {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?

Thanks!

答案1

得分: 6

我认为解决子集问题最常见的方法是使用映射。

  1. package main
  3. import "fmt"
  5. // subset函数返回true，如果第一个数组完全包含在第二个数组中。
  6. // 第二个数组中必须至少有与第一个数组中相同数量的重复值。
  7. func subset(first, second []int) bool {
  8.     set := make(map[int]int)
  9.     for _, value := range second {
  10.         set[value] += 1
  11.     }
  13.     for _, value := range first {
  14.         if count, found := set[value]; !found {
  15.             return false
  16.         } else if count < 1 {
  17.             return false
  18.         } else {
  19.             set[value] = count - 1
  20.         }
  21.     }
  23.     return true
  24. }
  26. func main() {
  27.     fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
  28.     fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
  29. }

检查重复值的能力相对较少见。上面的代码解决了所提出的问题（参见：http://play.golang.org/p/4_7Oh-fgDQ）。如果你计划有重复值，你将不得不像上面的代码那样保持一个计数。如果不会有重复值，你可以更简洁地通过使用布尔值作为映射值来解决问题。

英文:

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

  1. package main
  3. import &quot;fmt&quot;
  5. // subset returns true if the first array is completely
  6. // contained in the second array. There must be at least
  7. // the same number of duplicate values in second as there
  8. // are in first.
  9. func subset(first, second []int) bool {
  10. 	set := make(map[int]int)
  11. 	for _, value := range second {
  12. 		set[value] += 1
  13. 	}
  15. 	for _, value := range first {
  16. 		if count, found := set[value]; !found {
  17. 			return false
  18. 		} else if count &lt; 1 {
  19. 			return false
  20. 		} else {
  21. 			set[value] = count - 1
  22. 		}
  23. 	}
  25. 	return true
  26. }
  28. func main() {
  29. 	fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4}))
  30. 	fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
  31. }

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.

答案2

得分: 0

如果你的切片已经排序好，这段代码可以完成任务。

  1. package main
  3. import "fmt"
  5. // Subset 判断a是否是b的子列表。a和b都必须是（弱）升序的。
  6. func Subset(a, b []int) bool {
  7.     for len(a) > 0 {
  8.         switch {
  9.         case len(b) == 0:
  10.             return false
  11.         case a[0] == b[0]:
  12.             a = a[1:]
  13.             b = b[1:]
  14.         case a[0] < b[0]:
  15.             return false
  16.         case a[0] > b[0]:
  17.             b = b[1:]
  18.         }
  19.     }
  20.     return true
  21. }
  23. func main() {
  24.     cases := []struct {
  25.         a, b []int
  26.         want bool
  27.     }{
  28.         {[]int{1, 2, 3}, []int{1, 2, 3, 4}, true},
  29.         {[]int{1, 2, 2}, []int{1, 2, 3, 4}, false},
  30.     }
  31.     for _, c := range cases {
  32.         if Subset(c.a, c.b) != c.want {
  33.             fmt.Printf("Subset(%v, %v) = %v, want %v\n", c.a, c.b, Subset(c.a, c.b), c.want)
  34.         }
  35.     }
  36. }

这段代码定义了一个函数 Subset，用于判断切片 a 是否是切片 b 的子列表。切片 a 和 b 都必须是（弱）升序的。在 main 函数中，定义了一些测试用例，并通过调用 Subset 函数进行测试。如果测试结果与期望结果不一致，则输出错误信息。

英文:

If your slices are sorted, this does the job.

  1. package main
  3. import &quot;fmt&quot;
  5. // Subset return whether a is a sublist of b. Both a and b must be (weakly) ascending.
  6. func Subset(a, b []int) bool {
  7. 	for len(a) &gt; 0 {
  8. 		switch {
  9. 		case len(b) == 0:
  10. 			return false
  11. 		case a[0] == b[0]:
  12. 			a = a[1:]
  13. 			b = b[1:]
  14. 		case a[0] &lt; b[0]:
  15. 			return false
  16. 		case a[0] &gt; b[0]:
  17. 			b = b[1:]
  18. 		}
  19. 	}
  20. 	return true
  21. }
  23. func main() {
  24. 	cases := []struct {
  25. 		a, b []int
  26. 		want bool
  27. 	}{
  28. 		{[]int{1, 2, 3}, []int{1, 2, 3, 4}, true},
  29. 		{[]int{1, 2, 2}, []int{1, 2, 3, 4}, false},
  30. 	}
  31. 	for _, c := range cases {
  32. 		if Subset(c.a, c.b) != c.want {
  33. 			fmt.Printf(&quot;Subset(%v, %v) = %v, want %v\n&quot;, c.a, c.b, Subset(c.a, c.b), c.want)
  34. 		}
  35. 	}
  36. }

答案3

得分: -1

检查一个数组是否是另一个数组的子集的算法（使用golang）

  1. package main
  3. import "fmt"
  5. func compare(arr1 []int, arr2 []int) bool {
  6.     for _, num1 := range arr2 {
  7.         status := false
  8.         for _, num2 := range arr1 {
  9.             if num1 == num2 {
  10.                 status = true
  11.                 break
  12.             }
  13.         }
  14.         if !status {
  15.             return false
  16.         }
  17.     }
  18.     return true
  19. }
  21. func main() {
  22.     arr1 := []int{1, 2, 3, 4, 5}
  23.     arr2 := []int{1, 2, 3}
  24.     if compare(arr1, arr2) {
  25.         fmt.Println("arr2是arr1的子集")
  26.     } else {
  27.         fmt.Println("arr2不是arr1的子集")
  28.     }
  29. }

这段代码是用来检查一个数组是否是另一个数组的子集的。

英文:

Algorithm to check if an array is a subset of another array in golang

  1. package main
  3. import &quot;fmt&quot;
  5. func compare(arr1 []int, arr2 []int) bool {
  6. 	for _, num1 := range arr2 {
  7. 		status := false
  8. 		for _, num2 := range arr1 {
  9. 			if num1 == num2 {
  10. 				status = true
  11. 				break
  12. 			}
  13. 		}
  14. 		if !status {
  15. 			return false
  16. 		}
  17. 	}
  18. 	return true
  19. }
  20. func main() {
  21. 	arr1 := []int{1, 2, 3, 4, 5}
  22. 	arr2 := []int{1, 2, 3}
  23. 	if compare(arr1, arr2) {
  24. 		fmt.Println(&quot;arr2 is subset of arr1&quot;)
  25. 	} else {
  26. 		fmt.Println(&quot;arr2 is not subset of arr1&quot;)
  27. 	}
  28. }

huangapple
  • 本文由 发表于 2013年9月19日 01:57:36
  • 转载请务必保留本文链接：https://go.coder-hub.com/18879109.html
  • arrays
  • go
  • slice
  • subset
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定