tgoop.com/go_interview_lib/549
Create:
Last Update:
Last Update:
💬 Можно ли реализовать set на Go?
Set — это структура данных, которая хранит уникальные элементы и позволяет быстро проверять их наличие, добавлять и удалять их, без дубликатов. В Go нет встроенного типа для множеств, но мы можем использовать тип map с ключами нужного типа, а в качестве значения использовать struct{}, который не занимает память:
package main
import "fmt"
// Set — коллекция уникальных элементов
type Set struct {
elements map[string]struct{}
}
// NewSet создает новое множество
func NewSet() *Set {
return &Set{elements: make(map[string]struct{})}
}
// Add добавляет элемент
func (s *Set) Add(value string) {
s.elements[value] = struct{}{}
}
// Remove удаляет элемент
func (s *Set) Remove(value string) {
delete(s.elements, value)
}
// Contains проверяет наличие элемента
func (s *Set) Contains(value string) bool {
_, found := s.elements[value]
return found
}
// List возвращает все элементы в виде среза
func (s *Set) List() []string {
keys := make([]string, 0, len(s.elements))
for key := range s.elements {
keys = append(keys, key)
}
return keys
}
// Пример использования множества
func main() {
set := NewSet()
set.Add("apple")
set.Add("banana")
fmt.Println("Contains 'apple':", set.Contains("apple"))
fmt.Println("Set elements:", set.List())
set.Remove("banana")
fmt.Println("Set after removal:", set.List())
}
Основные операции с множествами:
- Union: создаёт множество, содержащее все элементы из двух множеств.
- Intersection: возвращает множество с элементами, общими для двух множеств.
- Difference: возвращает множество элементов, которые есть в первом множестве, но отсутствуют во втором.
Пример:
set1 := NewSet()
set1.Add("apple")
set1.Add("banana")
set2 := NewSet()
set2.Add("banana")
set2.Add("orange")
unionSet := set1.Union(set2)
fmt.Println("Union:", unionSet.List()) // ["apple", "banana", "orange"]
Производительность: все основные операции с помощью множеств (добавление, удаление, проверка) выполняются за время O(1) благодаря использованию мапы.
BY Библиотека Go для собеса | вопросы с собеседований
Share with your friend now:
tgoop.com/go_interview_lib/549