如何查找与其他数组相交的元素

Question

我有一个像这样的数组：

a:= [1,2,3,4,5]
b:= [5,6,7,8,9]

不使用foreach如何知道数组b包含数组a中的元素？

Answer 1

不使用foreach如何知道数组b包含数组a中的元素？

你不能。你不应该尝试，因为这是毫无意义的限制。

Answer 2

如果数组已排序（正如它们在您的问题中所示），则有一种算法比遍历每个元素效果更好。

选取

a

的第一个元素，称之为

x

。 二分查找

b

查找等于或大于

x

的第一个元素。如果它们相等，则您找到了两个数组中都包含的元素，如果不相等，则将其作为新的

x

。现在以同样的方式在

a

中搜索

x

。重复此操作，直到用完其中一个数组中的元素。

这可以简单地扩展到任意数量的数组（事实上，使用任意数量的数组编写更容易）。

这是一个快速但肮脏的实现：

package main

import (
    "fmt"
    "sort"
)

func inter(arrs ...[]int) []int {
    res := []int{}
    x := arrs[0][0]
    i := 1
    for {
        off := sort.SearchInts(arrs[i], x)
        if off == len(arrs[i]) {
            // we emptied one slice, we're done.
            break
        }
        if arrs[i][off] == x {
            i++
            if i == len(arrs) {
                // x was in all the slices
                res = append(res, x)
                x++ // search for the next possible x.
                i = 0
            }
        } else {
            x = arrs[i][off]
            i = 0 // This can be done a bit more optimally.
        }
    }
    return res
}

func main() {
    a := []int{1, 2, 3, 4, 5, 7}
    b := []int{5, 6, 7, 8, 9}

    fmt.Println(inter(a, b))
}

Answer 3

package main

import (
    set "github.com/deckarep/golang-set"
)

func array_intersect(a, b []interface{}) []interface{} {
    return set.NewSetFromSlice(a).Intersect(set.NewSetFromSlice(b)).ToSlice()
}
func main() {
    a := []interface{}{1, 2, 3, 4, 5, 7}
    b := []interface{}{5, 6, 7, 8, 9}

    println(array_intersect(a, b))
}

Answer 4

package main

import (
    "fmt"
    "sort"
)

func array_intersect(a, b []int) []int {
    ret := []int{}

    lenA := len(a)
    lenB := len(b)
    if lenA == 0 || lenB == 0 {
        return ret
    }
    sort.Ints(a)
    sort.Ints(b)
    var i, j int
    for {
        a = a[i:]
        if i = sort.SearchInts(a, b[j]); i >= len(a) {
            break
        }
        if a[i] == b[j] {
            ret = append(ret, a[i])
        }
        if j++; j >= lenB {
            break
        }
    }

    return ret
}
func main() {
    a := []int{5, 7, 1, 1, 2, 3, 4, 5, 7}
    b := []int{1, 1, 5, 6, 7, 8, 9}
    fmt.Printf("a=%v, b=%v", a, b)
    fmt.Printf("%v\n", array_intersect(a, b))
    fmt.Printf("a=%v, b=%v", a, b)
}