数据结构：集合 - Golang-Golang-PHP中文网

数据结构：集合 - Golang

WBOY

发布： 2024-07-20 12:17:08

原创

402 人浏览过

Estrutura de dados: Set - Golang

大家好，你们好吗？今天我想带来Go相关的内容，其中包括创建一个名为Set的数据结构。

毕竟，什么是 Set？

集合是一个线性数据集，具有非重复值的集合。 Set 可以以无特定顺序存储唯一值。

毕竟Go中有Set吗？

答案是否定的。例如，在 Go 中，我们没有像 Java 或 C# 中那样的 Set 或 HashSet 数据结构。但是拥有 Terraform 的大型科技公司 Hashicorp 有一个库可以在 Go 世界中为我们解决此类问题。我将在文章末尾留下存储库链接。

Set解决了什么问题？

成员资格检查：设置擅长快速检查其中是否存在元素。这是因为集合经常使用哈希技术进行快速查找，为成员资格检查提供 O(1) 的平均时间复杂度。
查找唯一元素：使用集合来计算或查找列表中的不同元素变得高效。只需将所有元素添加到一个集合中，它就只包含唯一的条目。这消除了复杂的比较循环的需要。
集合操作：集合提供内置操作函数，例如并集（组合两个集合中的元素）、交集（查找两个集合中共有的元素）和差值（一个集合中的元素，但不是另一个集合中的元素）。这些操作对于数据操作和分析非常有用。
以下是一些具体的问题示例，其中集合可能是一个不错的选择：
查找列表中的重复元素：将所有元素添加到集合中。如果集合大小小于原始列表大小，则存在重复。
查找两个列表的交集：使用集合交集运算查找两个列表中都存在的元素。
识别数据集中的频繁元素：将元素添加到集合中并计算它们的出现次数。该集合消除了重复项，让您能够专注于独特的元素及其频率。
检查字符串是否为回文：将字符串转换为集合并检查其大小。如果去重后大小保持不变，则为回文（所有字符只出现一次）。

好吧，我将用一种新的方式来解释代码，即通过注释来解释代码内部的流程。

import "fmt"

// Criamos nossa estrutura para definir um map
type Set struct {
    integerMap map[int]bool
}

// Criamos nosso "construtor" para inicializar o map
func (s *Set) newSet() {
    s.integerMap = make(map[int]bool)
}

// Aqui temos a função que vai verificar se o elemento é false, por padrão é sempre falso, e se o elemento retornar false é porque esse valor não existe no nosso map e então podemos adicioná-lo. Mas se essa função retornar true, no nosso addElement ele nem vai adicionar ao mapa.
func (s *Set) containsElement(el int) bool {
    var exists bool
    _, exists = s.integerMap[el]
    return exists
}

// Responsável pela adição do elemento no mapa.
// Aqui, esse if verifica se o elemento contido é falso; se for falso, ele não tem uma duplicata e então pode ser adicionado à lista.
// Agora, se o resultado de contains for true, ele nem vai cair dentro desse if e por tanto não vai adicionar a lista.
func (s *Set) addElement(el int) {
    if !s.containsElement(el) {
        s.integerMap[el] = true
    }
}

// Aqui um delete simples
func (s *Set) deleteEl(el int) {
    delete(s.integerMap, el)
}

// Aqui damos um findAll que lista todos os elementos, sendo seu Big O O(n)
func (s *Set) allElements() {
    for k := range s.integerMap {
        fmt.Println(k)
    }
}

// Aqui temos a função que tem o length, que vai ser o tamanho do nosso integerMap, e a variável c, que pode ser chamada de collection, pois vai ser nossa coleção das chaves do nosso map, ou seja, uma lista.
// Dentro do nosso for, fazemos esse loop para descobrir se c[x] é maior do que c[n + 1], ou seja, a próxima posição na nossa lista.
// Criamos o initialValue que vai ser o valor em relação à posição da lista.
// Depois, atribuimos a c[x] o próximo valor da iteração, ou seja, c[x+1].
// E por fim, atribuimos o valor de c[x+1] = initialValue.
// Assim, fazemos com que os maiores valores da lista sejam trocados, jogando os maiores para o final da lista. O maior número SEMPRE tem que estar no fim da lista.
// Em outros termos, estamos fazendo uma ordenação por bolha ou bubblesort.
// Seu Big O é de O(n) no melhor caso e no pior caso é O(n^2).
// Mas sua complexidade espacial é muito boa, sendo O(1).
func (s *Set) maximumElements() {
    length := len(s.integerMap)

    c := s.allElements()

    for n := 0; x < length-1; x++ {
        if c[x] > c[x+1] {
            initialValue := c[x]
            c[x] = c[x+1]
            c[x+1] = initialValue
        }
    }
    maximumValue := c[length-1]
    fmt.Printf("MaximumValue: %d\n", maximumValue)
}

// Com a explicação do maximumElements, aqui é a mesma coisa,só que o menor número também tem que estar no final da lista.
func (s *Set) minumumElements() {

    c := s.allElements()
    length := len(s.integerMap)

    for x := 0; x < length-1; x++ {
        if c[x] < c[x+1] {
            initialValue := c[x]
            c[x] = c[x+1]
            c[x+1] = initialValue
        }
    }

    m := c[length-1]
    fmt.Printf("Minimum value %d\n", m)
}

// aqui temos nosso sizeOfSet que basicamente vai printar na tela o tamanho do nossa lista
func (s *Set) sizeOfSet() {
    fmt.Printf("Length of List: %v\n", len(s.allElements()))
}

func printValues(values []int) {

    fmt.Printf("List of Values: %v\n", values)
}

func main() {
    set := &Set{}
    set.newSet()
    set.addElement(3)
    set.addElement(6)
    set.addElement(8)
    set.addElement(9)
    set.addElement(10)
    set.addElement(14)
    set.addElement(3)
    set.addElement(2)
    set.addElement(14)

    values := set.allElements()
    printValues(values)

    set.maximumElements()
    set.minumumElements()

    fmt.Printf("Contains Value: %v\n", set.containsElement(1))

    set.sizeOfSet()

    set.deleteElements(14)
    set.deleteElements(2)
    fmt.Println("--------------------------------")
    valuesAfterDelete := set.allElements()
    set.maximumElements()
    set.minumumElements()
    printValues(valuesAfterDelete)
}

登录后复制

控制台响应

List of Values: [8 9 10 14 2 3 6]
MaximumValue: 14
Minimum value: 2
Contains Value: false
Length of List: 7
--------------------------------
MaximumValue: 10
Minimum value: 3
List of Values: [9 10 3 6 8]

登录后复制