Что такое множество?

В этом уроке ты

Узнаешь, что такое множество.
Научишься использовать его в своём языке программирования.
Решишь задачу с использованием множества.

Знакомство с множеством

Множество (хеш-сет) — это одна из ключевых структур данных, которая используется для хранения уникальных элементов без соблюдения их порядка.

Как ты узнал из предыдущей лекции, хеш-таблица хранит пары "ключ — значение", тогда как множество содержит только уникальные ключи без значений. Это позволяет экономить память в задачах, где нужно хранить только ключи.

Множество в твоём языке программирования

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        HashSet<int> hashSet = new HashSet<int>();

        // Вставка
        hashSet.Add(1);

        // Проверка наличия
        Console.WriteLine(hashSet.Contains(1)); // true

        // Удаление
        hashSet.Remove(1);

        // Узнать размер
        Console.WriteLine(hashSet.Count);
    }
}

#include <iostream>
#include <unordered_set>

int main() {
    std::unordered_set<int> hashSet;

    // Вставка
    hashSet.insert(1);

    // Проверка наличия
    std::cout << (hashSet.find(1) != hashSet.end()) << std::endl;  // true

    // Удаление
    hashSet.erase(1);

    // Узнать размер
    std::cout << hashSet.size() << std::endl;

    return 0;
}

package main

import (
    "fmt"
)

func main() {
    hashSet := make(map[int]bool)

    // Вставка
    hashSet[1] = true

    // Проверка наличия
    _, exists := hashSet[1]
    fmt.Println(exists) // true

    // Удаление
    delete(hashSet, 1)

    // Узнать размер
    fmt.Println(len(hashSet))
}

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();

        // Вставка
        hashSet.add(1);

        // Проверка наличия
        System.out.println(hashSet.contains(1)); // true

        // Удаление
        hashSet.remove(1);

        // Узнать размер
        System.out.println(hashSet.size());
    }
}

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<Integer> hashSet = new HashSet<>();

        // Вставка
        hashSet.add(1);

        // Проверка наличия
        System.out.println(hashSet.contains(1)); // true

        // Удаление
        hashSet.remove(1);

        // Узнать размер
        System.out.println(hashSet.size());
    }
}

hash_set = set()

# Вставка
hash_set.add(1)

# Проверка наличия
print(1 in hash_set)  # True

# Удаление
hash_set.remove(1)  # Если элемента нет, вызывает KeyError
# hash_set.discard(1)  # Удаляет без ошибки, если элемента нет

# Узнать размер
print(len(hash_set))

Задача на поиск повторяющихся элементов

Подобная задача может встретиться не только на собеседовании, но и в реальной работе. Каждый разработчик должен знать, как быстро и эффективно находить совпадающие элементы. Давай разберемся!

Условие

Дан массив целых чисел nums. Надо вернуть true, если массив содержит повторяющиеся элементы и false, если нет.

Пример 1

Ввод: nums = [1,3,5,2,5]
Вывод: true
Объяснение: элемент 5 встречается два раза

Пример 2

Ввод: nums = [3,5,7,9]
Вывод: false
Объяснение: все элементы уникальны

Решение с использованием хеш-таблицы

При решении с использованием хеш-таблицы значение элемента из массива используется в качестве ключа, а в качестве значения записывается true, как индикатор того, что данный элемент ранее встречался.

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
function containsDuplicate(nums) {
    // Создаем хеш-таблицу
    const used = {};
    for (let num of nums) {
        // Проверяем наличие в хеш-таблице
        if (num in used) {
            return true;
        }
        // Добавляем элемент в хеш-таблицу
        used[num] = true;
    }
    return false;
}

#include <vector>
#include <unordered_map>

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
bool containsDuplicate(std::vector<int>& nums) {
    // Создаем хеш-таблицу
    std::unordered_map<int, bool> used;
    for (int num : nums) {
        // Проверяем наличие в хеш-таблице
        if (used.find(num) != used.end()) {
            return true;
        }
        // Добавляем элемент в хеш-таблицу
        used[num] = true;
    }
    return false;
}

package main

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
func containsDuplicate(nums []int) bool {
    // Создаем хеш-таблицу
    used := make(map[int]bool)
    for _, num := range nums {
        // Проверяем наличие в хеш-таблице
        if _, exists := used[num]; exists {
            return true
        }
        // Добавляем элемент в хеш-таблицу
        used[num] = true
    }
    return false
}

import java.util.HashMap;
import java.util.List;

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
class Solution {
    public boolean containsDuplicate(int[] nums) {
        // Создаем хеш-таблицу
        HashMap<Integer, Boolean> used = new HashMap<>();
        for (int num : nums) {
            // Проверяем наличие в хеш-таблице
            if (used.containsKey(num)) {
                return true;
            }
            // Добавляем элемент в хеш-таблицу
            used.put(num, true);
        }
        return false;
    }
}

#Время: O(n), где n — размер входного массива.
#Память: O(n), где n — размер входного массива.
def contains_duplicate(nums: List[int]) -> bool:
    # Создаем хеш-таблицу
    used = dict()
    for num in nums:
        # Проверяем наличие в хеш-таблице
        if num in used:
            return True
        # Добавляем элемент в хеш-таблицу
        used[num] = True
    return False

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
function containsDuplicate(nums) {
    // Создаем хеш-таблицу
    const used = {};
    for (let num of nums) {
        // Проверяем наличие в хеш-таблице
        if (num in used) {
            return true;
        }
        // Добавляем элемент в хеш-таблицу
        used[num] = true;
    }
    return false;
}

Такое решение абсолютно верное, но расходует чуть больше памяти, потому что нам надо хранить и ключ, и значение. Поэтому в таких случаях лучше использовать множество.

Решение с использованием множества

using System;
using System.Collections.Generic;

class Solution
{
    public bool ContainsDuplicate(int[] nums)
    {
        // Создаем множество
        HashSet<int> used = new HashSet<int>();
        
        foreach (int num in nums)
        {
            // Проверяем наличие в множестве
            if (used.Contains(num))
            {
                return true;
            }
            // Добавляем элемент в множество
            used.Add(num);
        }
        
        return false;
    }
}

#include <vector>
#include <unordered_set>

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
bool containsDuplicate(std::vector<int>& nums) {
    // Создаем множество
    std::unordered_set<int> used;
    for (int num : nums) {
        // Проверяем наличие в множестве
        if (used.find(num) != used.end()) {
            return true;
        }
        // Добавляем элемент в множество
        used.insert(num);
    }
    return false;
}

package main

// Время: O(n), где n — размер входного массива.
// Память: O(n), где n — размер входного массива.
func containsDuplicate(nums []int) bool {
    // В Go принято использовать map[int]struct{} в качестве множества
    used := make(map[int]struct{})
    for _, num := range nums {
        // Проверяем наличие
        if _, ok := used[num]; ok {
            return true
        }
        // Добавляем элемент
        used[num] = struct{}{}
    }
    return false
}

import java.util.HashSet;
import java.util.List;

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
class Solution {
    public boolean containsDuplicate(int[] nums) {
                // Создаем множество
        HashSet<Integer> used = new HashSet<>();
        
        for (int num : nums) {
            // Проверяем наличие в множестве
            if (used.contains(num)) {
                return true;
            }
            // Добавляем элемент в множество
            used.add(num);
        }
        
        return false;
    }
}

import java.util.HashSet;
import java.util.List;

//Время: O(n), где n — размер входного массива.
//Память: O(n), где n — размер входного массива.
class Solution {
    public boolean containsDuplicate(int[] nums) {
                // Создаем множество
        HashSet<Integer> used = new HashSet<>();
        
        for (int num : nums) {
            // Проверяем наличие в множестве
            if (used.contains(num)) {
                return true;
            }
            // Добавляем элемент в множество
            used.add(num);
        }
        
        return false;
    }
}

#Время: O(n), где n — размер входного массива.
#Память: O(n), где n — размер входного массива.
def contains_duplicate(nums: List[int]) -> bool:
    # Создаем множество
    used = set()
    for num in nums:
        # Проверяем наличие в множестве
        if num in used:
            return True
        # Добавляем элемент в множество
        used.add(num)
    return False

Какое решение лучше?

Оба решения являются верными, но использование множества, хранящего только ключи, является более предпочтительным, так как это позволяет экономить память за счет исключения хранения значений.

Заключение

На этой лекции мы познакомились с множеством, изучили принцип его работы и решили задачу. Теперь приступай к практической части, чтобы закрепить свои знания!