PrepBro
← Назад к вопросам

Реализация Set на основе List

2.0 Middle🔥 121 комментариев
#Коллекции и структуры данных#Тестирование

Условие

Реализовать структуру данных Set с использованием List в качестве внутреннего хранилища.

Интерфейс:

class MySet<T> {
    fun count(): Int  // количество элементов
    fun add(element: T): Boolean  // true если добавлен
    fun remove(element: T): Boolean  // true если удалён
    fun contains(element: T): Boolean
    fun clear()
}

Требования:

  1. Не использовать стандартные Set реализации
  2. Элементы не должны дублироваться
  3. add() возвращает false если элемент уже есть
  4. remove() возвращает false если элемента нет

Тесты:

val set = MySet<Int>()
assert(set.add(1) == true)
assert(set.add(1) == false)
assert(set.count() == 1)
assert(set.contains(1) == true)
assert(set.remove(1) == true)
assert(set.remove(1) == false)

Бонус:

  • Реализовать итератор
  • Добавить операции union, intersection, difference
  • Оценить сложность операций

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение: Реализация Set на основе List

1. Базовая реализация MySet

class MySet<T> {
    private val elements: MutableList<T> = mutableListOf()
    
    fun count(): Int = elements.size
    
    fun add(element: T): Boolean {
        if (contains(element)) {
            return false
        }
        elements.add(element)
        return true
    }
    
    fun remove(element: T): Boolean {
        return elements.remove(element)
    }
    
    fun contains(element: T): Boolean {
        return elements.contains(element)
    }
    
    fun clear() {
        elements.clear()
    }
    
    fun isEmpty(): Boolean = elements.isEmpty()
    
    fun toList(): List<T> = elements.toList()
}

2. Реализация с итератором

class MySet<T> : Iterable<T> {
    private val elements: MutableList<T> = mutableListOf()
    
    fun count(): Int = elements.size
    
    fun add(element: T): Boolean {
        if (contains(element)) return false
        elements.add(element)
        return true
    }
    
    fun remove(element: T): Boolean {
        return elements.remove(element)
    }
    
    fun contains(element: T): Boolean {
        return elements.contains(element)
    }
    
    fun clear() {
        elements.clear()
    }
    
    override fun iterator(): Iterator<T> = elements.iterator()
    
    fun toList(): List<T> = elements.toList()
}

3. Операции над множествами

class MySet<T> : Iterable<T> {
    private val elements: MutableList<T> = mutableListOf()
    
    fun count(): Int = elements.size
    
    fun add(element: T): Boolean {
        if (contains(element)) return false
        elements.add(element)
        return true
    }
    
    fun remove(element: T): Boolean {
        return elements.remove(element)
    }
    
    fun contains(element: T): Boolean {
        return elements.contains(element)
    }
    
    fun clear() {
        elements.clear()
    }
    
    fun union(other: MySet<T>): MySet<T> {
        val result = MySet<T>()
        elements.forEach { result.add(it) }
        other.elements.forEach { result.add(it) }
        return result
    }
    
    fun intersection(other: MySet<T>): MySet<T> {
        val result = MySet<T>()
        elements.forEach { element ->
            if (other.contains(element)) {
                result.add(element)
            }
        }
        return result
    }
    
    fun difference(other: MySet<T>): MySet<T> {
        val result = MySet<T>()
        elements.forEach { element ->
            if (!other.contains(element)) {
                result.add(element)
            }
        }
        return result
    }
    
    fun isSubsetOf(other: MySet<T>): Boolean {
        return elements.all { other.contains(it) }
    }
    
    fun isSupersetOf(other: MySet<T>): Boolean {
        return other.isSubsetOf(this)
    }
    
    override fun iterator(): Iterator<T> = elements.iterator()
    
    override fun equals(other: Any?): Boolean {
        if (this === other) return true
        if (other !is MySet<*>) return false
        if (count() != other.count()) return false
        return elements.all { other.contains(it) }
    }
    
    override fun hashCode(): Int {
        return elements.fold(0) { acc, element ->
            acc + (element?.hashCode() ?: 0)
        }
    }
    
    override fun toString(): String = elements.toString()
}

4. Unit Тесты

class MySetTest {
    @Test
    fun testAddElement() {
        val set = MySet<Int>()
        assertTrue(set.add(1))
        assertEquals(1, set.count())
    }
    
    @Test
    fun testAddDuplicate() {
        val set = MySet<Int>()
        assertTrue(set.add(1))
        assertFalse(set.add(1))
        assertEquals(1, set.count())
    }
    
    @Test
    fun testContains() {
        val set = MySet<Int>()
        set.add(1)
        assertTrue(set.contains(1))
        assertFalse(set.contains(2))
    }
    
    @Test
    fun testRemove() {
        val set = MySet<Int>()
        set.add(1)
        assertTrue(set.remove(1))
        assertFalse(set.remove(1))
        assertEquals(0, set.count())
    }
    
    @Test
    fun testClear() {
        val set = MySet<Int>()
        set.add(1)
        set.add(2)
        set.clear()
        assertEquals(0, set.count())
    }
    
    @Test
    fun testUnion() {
        val set1 = MySet<Int>()
        val set2 = MySet<Int>()
        set1.add(1)
        set1.add(2)
        set2.add(2)
        set2.add(3)
        
        val union = set1.union(set2)
        assertEquals(3, union.count())
        assertTrue(union.contains(1))
        assertTrue(union.contains(2))
        assertTrue(union.contains(3))
    }
    
    @Test
    fun testIntersection() {
        val set1 = MySet<Int>()
        val set2 = MySet<Int>()
        set1.add(1)
        set1.add(2)
        set1.add(3)
        set2.add(2)
        set2.add(3)
        set2.add(4)
        
        val intersection = set1.intersection(set2)
        assertEquals(2, intersection.count())
        assertTrue(intersection.contains(2))
        assertTrue(intersection.contains(3))
        assertFalse(intersection.contains(1))
    }
    
    @Test
    fun testDifference() {
        val set1 = MySet<Int>()
        val set2 = MySet<Int>()
        set1.add(1)
        set1.add(2)
        set1.add(3)
        set2.add(2)
        set2.add(4)
        
        val difference = set1.difference(set2)
        assertEquals(2, difference.count())
        assertTrue(difference.contains(1))
        assertTrue(difference.contains(3))
        assertFalse(difference.contains(2))
    }
    
    @Test
    fun testIterator() {
        val set = MySet<Int>()
        set.add(1)
        set.add(2)
        set.add(3)
        
        val elements = set.toList()
        assertEquals(3, elements.size)
        assertTrue(elements.contains(1))
    }
    
    @Test
    fun testEquality() {
        val set1 = MySet<Int>()
        val set2 = MySet<Int>()
        set1.add(1)
        set1.add(2)
        set2.add(2)
        set2.add(1)
        
        assertEquals(set1, set2)
    }
}

5. Анализ сложности операций

ОперацияСложностьПримечание
addO(n)Проверка contains + добавление
removeO(n)Линейный поиск элемента
containsO(n)Линейный поиск в списке
countO(1)Возврат размера
clearO(1)Очистка списка
unionO(n*m)Для каждого элемента проверка
intersectionO(n*m)Двойной перебор элементов
differenceO(n*m)Двойной перебор элементов

Оптимизация производительности

Для оптимизации можно использовать HashMap:

class OptimizedSet<T> {
    private val map = mutableMapOf<T, Boolean>()
    
    fun add(element: T): Boolean {
        if (contains(element)) return false
        map[element] = true
        return true
    }
    
    fun contains(element: T): Boolean {
        return map.containsKey(element)
    }
}

Это уменьшит сложность операций до O(1) в среднем случае.

Ключевые особенности

  • Уникальность элементов: Автоматически обеспечивается проверкой contains
  • Итератор: Позволяет перебирать элементы
  • Операции над множествами: union, intersection, difference
  • Равенство: Два набора равны если содержат одни элементы
  • Простота: Чистая реализация на List

Это полнофункциональная реализация Set с полной поддержкой операций над множествами.

Реализация Set на основе List | PrepBro