在Go语言切片或数组中查找唯一项

vq8itlhq  于 2023-03-06  发布在  Go
关注(0)|答案(4)|浏览(159)

我是新来的,我现在真的很困惑。
假设我有一个坐标列表,并且在这个坐标列表中有一些双精度数,我一辈子都想不出如何创建一个唯一的列表,通常在Python中,我可以用集合和其他内置函数“作弊”,但在Go语言中就不太可能了。

package main

import (
    "fmt"
    "reflect"
)

type visit struct {
    x, y int
}

func main() {
    var visited []visit
    var unique []visit

    visited = append(visited, visit{1, 100})
    visited = append(visited, visit{2, 2})
    visited = append(visited, visit{1, 100})
    visited = append(visited, visit{1, 1})

    unique = append(unique, visit{1, 1})

    fmt.Println(unique)

    // Go through the visits and find the unique elements
    for _, v := range visited {
        for _, u := range unique {

            fmt.Printf("Here's unique: %v\n", unique)
            fmt.Printf("Comparing %v to %v is %v\n", v, u, reflect.DeepEqual(v, u))

            if reflect.DeepEqual(v, u) {
                fmt.Println("Skip")
            } else {
                unique = append(unique, v)
            }
        }
    }

    fmt.Println(unique)
}

Run it on Playground

eimct9ow

eimct9ow1#

你的代码中有多个错误。最严重的是,因为你将visited切片的每个特定元素与unique所有元素进行比较,如果unique包含至少一个不同的元素,你将最终追加它。如果在unique中有更多的元素,而这些元素与内部for循环不"中断"不同,那么最终将多次追加它。这不是您想要的,您希望追加等于uniquenone的元素。
还要注意的是,如果struct的每个字段都是可比较的,那么它就是可比较的。因为你的visit结构体只包含2个int字段,所以它是可比较的,所以你可以简单地用==操作符来比较visit类型的值,而不需要那么难看的reflect.DeepEqual()。参见Spec:比较运算符:
如果结构值的所有字段都可比较,则结构值可比较。如果两个结构值对应的非空字段相等,则两个结构值相等。
下面是一个简化的、正确的版本,可以应用你的逻辑:

visited := []visit{
    visit{1, 100},
    visit{2, 2},
    visit{1, 100},
    visit{1, 1},
}
var unique []visit

for _, v := range visited {
    skip := false
    for _, u := range unique {
        if v == u {
            skip = true
            break
        }
    }
    if !skip {
        unique = append(unique, v)
    }
}

fmt.Println(unique)

输出(在Go Playground上尝试):

[{1 100} {2 2} {1 1}]

备选

Go语言确实没有内置的集合类型,但是你可以很容易地将map[visit]bool作为集合使用,这样就变得非常简单了!注意,visit可以作为map中的键,因为它是可比较的(见上文)。

visited := []visit{
    visit{1, 100},
    visit{2, 2},
    visit{1, 100},
    visit{1, 1},
}
unique := map[visit]bool{}

for _, v := range visited {
    unique[v] = true
}

fmt.Println(unique)

输出(在Go Playground上尝试):

map[{2 2}:true {1 1}:true {1 100}:true]

唯一的"列表"是Map中键的列表。
如果希望将唯一的visit值作为一个切片,请参见以下变体:

var unique []visit
m := map[visit]bool{}

for _, v := range visited {
    if !m[v] {
        m[v] = true
        unique = append(unique, v)
    }
}

fmt.Println(unique)

输出(如预期,在Go Playground上尝试):

[{1 100} {2 2} {1 1}]

请注意,此索引表达式:如果v已在Map中,则m[v]的计算结果为true(作为键,true是我们存储在map中的值)。如果v还没有在map中,m[v]产生值类型的零值,对于类型boolfalse。正确告知值v尚未在Map中。参见规范:索引表达式:
对于Map类型为M的:
...如果Map为nil或不包含此类条目,则a[x]是值类型M的零值

g0czyy6m

g0czyy6m2#

我想你可以去拜访很多次就像这样

visited := make(map[visit]Boolean)

您可以设置访问的值。

visited[visit]=true

最后,您可以通过此代码获取所有访问过的位置

for k, _ := range visited {
    unique = append(unique, k)
}
laximzn5

laximzn53#

我想你可以借助Map来解决这个难题
https://play.golang.org/p/b7JtHYQ3N8

package main

import (
    "fmt"
)

type visit struct {
    x, y int
}

func main() {
    var visited []visit
    var unique []visit

    uniqueMap := map[visit]int{}

    visited = append(visited, visit{1, 100})
    visited = append(visited, visit{2, 2})
    visited = append(visited, visit{1, 100})
    visited = append(visited, visit{1, 1})

    for _, v := range visited {
        if _, exist := uniqueMap[v]; !exist {
            uniqueMap[v] = 1
            unique = append(unique, v)
        } else {
            uniqueMap[v]++
        }
    }
    fmt.Printf("Uniques: %v\nMaps:%v\n", unique, uniqueMap)
}
klr1opcd

klr1opcd4#

您可以通过sort.Slice()对切片进行排序,然后通过用以下唯一元素覆盖非唯一元素来使切片唯一:

func Unique[T comparable](xs []T) []T {
    n := len(xs)
    if n == 0 {
        return xs
    }
    j := 0
    for i := 1; i < n; i++ {
        if xs[j] !=  xs[i] {
            j++
            if j < i {
                xs[j] = xs[i]
                for k := i + 1; k < n; k++ {
                    if xs[j] !=  xs[k] {
                        j++
                        xs[j] = xs[k]
                    }
                }
                break
            }
        }
    }
    xs = xs[0:j+1]
    return xs
}

使切片唯一只是线性的工作,然而,这主要是排序(除非您的输入已经排序),它在O(n log n)中。
示例用法:

visited = sort.Slice(visited, func(i, j int) bool {
        return visited[i].x < visited[j].x && visited[i].y < visited[j].y })
visited = Unique(visited)
unique := visited

或者,如果不想排序或不关心元素顺序,可以将所有元素存储在一个类似集合的Map中,这样可以消除重复。
示例:

h := map[visit]struct{} {}
for _, v := range visited {
    h[v] = struct{} {}
}
unique := make(visit[], len(h))
i := 0
for k := range h {
    unique[i] = k
    i++
}

总的运行时间是线性的,除非您的数据散列错误。

相关问题