EasyПрактика12 min

HashSet: уникальность и поиск

Использование множеств для задач на уникальность, пересечение и разность

AlgoHash tables

Что такое HashSet?

HashSet — это коллекция уникальных элементов с O(1) проверкой принадлежности. По сути — HashMap, где хранятся только ключи (без значений).

<?php
declare(strict_types=1);

// PHP: associative array with true values (or array_flip)
$set = [];
$set[1] = true;
$set[2] = true;
$set[3] = true;
$set[4] = true;       // {1, 2, 3, 4}
$set[2] = true;       // {1, 2, 3, 4} — duplicate ignored
isset($set[2]);        // true — O(1)
unset($set[3]);        // {1, 2, 4}

// Alternative: array_flip for creating set from array
$set = array_flip([1, 2, 3, 4]);
isset($set[2]); // true — O(1)
## Операции с множествами
Операция PHP Сложность
Добавить $s[$x] = true O(1)
Удалить unset($s[$x]) O(1)
Проверка isset($s[$x]) O(1)
Объединение $s1 + $s2 O(n+m)
Пересечение array_intersect_key($s1, $s2) O(min(n,m))
Разность array_diff_key($s1, $s2) O(n) 
Множество A: {1, 2, 3, 4}
Множество B: {3, 4, 5, 6}

A | B = {1, 2, 3, 4, 5, 6}   (объединение)
A & B = {3, 4}                 (пересечение)
A - B = {1, 2}                 (разность)
A ^ B = {1, 2, 5, 6}          (симметричная разность)

Задача 1: Contains Duplicate

<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 */
function containsDuplicate(array $nums): bool
{
    return count($nums) !== count(array_unique($nums));
}

// Or explicitly:
/**
 * @param int[] $nums
 */
function containsDuplicateV2(array $nums): bool
{
    $seen = [];
    foreach ($nums as $num) {
        if (isset($seen[$num])) {
            return true;
        }
        $seen[$num] = true;
    }
    return false;
}

// [1, 2, 3, 1] -> true
// [1, 2, 3, 4] -> false
## Задача 2: Intersection of Two Arrays 
<?php
declare(strict_types=1);

/**
 * @param int[] $nums1
 * @param int[] $nums2
 * @return int[]
 */
function intersection(array $nums1, array $nums2): array
{
    $set1 = array_flip($nums1);
    $set2 = array_flip($nums2);
    return array_keys(array_intersect_key($set1, $set2));
}

// nums1 = [1,2,2,1], nums2 = [2,2] -> [2]
// nums1 = [4,9,5], nums2 = [9,4,9,8,4] -> [9,4]
### С сохранением количества (Intersection II) 
<?php
declare(strict_types=1);

/**
 * @param int[] $nums1
 * @param int[] $nums2
 * @return int[]
 */
function intersect(array $nums1, array $nums2): array
{
    $count = array_count_values($nums1);
    $result = [];

    foreach ($nums2 as $num) {
        if (($count[$num] ?? 0) > 0) {
            $result[] = $num;
            $count[$num]--;
        }
    }

    return $result;
}

// nums1 = [1,2,2,1], nums2 = [2,2] -> [2,2]
## Задача 3: Single Number

Условие: каждый элемент встречается дважды, кроме одного. Найти его.

<?php
declare(strict_types=1);

// Solution via Set:
/**
 * @param int[] $nums
 */
function singleNumberSet(array $nums): int
{
    $seen = [];
    foreach ($nums as $num) {
        if (isset($seen[$num])) {
            unset($seen[$num]);
        } else {
            $seen[$num] = true;
        }
    }
    return array_key_first($seen);
}

// Optimal solution: XOR (O(1) memory)
/**
 * @param int[] $nums
 */
function singleNumberXor(array $nums): int
{
    $result = 0;
    foreach ($nums as $num) {
        $result ^= $num;
    }
    return $result;
}

// [2, 2, 1] -> 1
// [4, 1, 2, 1, 2] -> 4
// 4^1^2^1^2 = 4^(1^1)^(2^2) = 4^0^0 = 4
## Задача 4: Happy Number

Условие: число «счастливое», если последовательность сумм квадратов цифр приводит к 1.

<?php
declare(strict_types=1);

function isHappy(int $n): bool
{
    $seen = [];

    while ($n !== 1) {
        if (isset($seen[$n])) {
            return false; // Cycle detected
        }
        $seen[$n] = true;

        // Sum of squares of digits
        $total = 0;
        while ($n > 0) {
            $digit = $n % 10;
            $total += $digit * $digit;
            $n = intdiv($n, 10);
        }
        $n = $total;
    }

    return true;
}

// n = 19:
// 1^2 + 9^2 = 82
// 8^2 + 2^2 = 68
// 6^2 + 8^2 = 100
// 1^2 + 0^2 + 0^2 = 1 -> true!

// n = 2:
// 4 -> 16 -> 37 -> 58 -> 89 -> 145 -> 42 -> 20 -> 4 -> CYCLE! false
## Задача 5: Valid Sudoku 
<?php
declare(strict_types=1);

/**
 * @param string[][] $board
 */
function isValidSudoku(array $board): bool
{
    $rows = array_fill(0, 9, []);
    $cols = array_fill(0, 9, []);
    $boxes = array_fill(0, 9, []);

    for ($i = 0; $i < 9; $i++) {
        for ($j = 0; $j < 9; $j++) {
            $num = $board[$i][$j];
            if ($num === '.') {
                continue;
            }

            $boxIdx = intdiv($i, 3) * 3 + intdiv($j, 3);

            if (isset($rows[$i][$num]) || isset($cols[$j][$num]) || isset($boxes[$boxIdx][$num])) {
                return false;
            }

            $rows[$i][$num] = true;
            $cols[$j][$num] = true;
            $boxes[$boxIdx][$num] = true;
        }
    }

    return true;
}
## Задача 6: Missing Number 
<?php
declare(strict_types=1);

// Via Set:
/**
 * @param int[] $nums
 */
function missingNumberSet(array $nums): int
{
    $set = array_flip($nums);
    $n = count($nums);
    for ($i = 0; $i <= $n; $i++) {
        if (!isset($set[$i])) {
            return $i;
        }
    }
    return $n;
}

// Via math (better):
/**
 * @param int[] $nums
 */
function missingNumberMath(array $nums): int
{
    $n = count($nums);
    $expectedSum = intdiv($n * ($n + 1), 2);
    return $expectedSum - array_sum($nums);
}

// Via XOR (O(1) memory):
/**
 * @param int[] $nums
 */
function missingNumberXor(array $nums): int
{
    $result = count($nums);
    foreach ($nums as $i => $num) {
        $result ^= $i ^ $num;
    }
    return $result;
}

// [3, 0, 1] -> 2
// [0, 1] -> 2
## Когда использовать Set vs HashMap
Задача Структура
Проверка «был ли такой элемент» Set
Подсчёт количества HashMap
Поиск комплемента с индексом HashMap
Обнаружение цикла Set
Уникальные элементы Set
Группировка по ключу HashMap
Пересечение/объединение множеств Set
Маппинг ключ-значение HashMap

Set через ассоциативный массив

<?php
declare(strict_types=1);

// PHP has no built-in Set class — use associative array

// Create set from array
$set = array_flip([1, 2, 3, 4, 5]);

// Check membership: O(1)
isset($set[3]); // true

// Add element
$set[6] = true;

// Remove element
unset($set[3]);

// Set operations
$a = array_flip([1, 2, 3, 4]);
$b = array_flip([3, 4, 5, 6]);

$union = $a + $b;                           // Union
$intersect = array_intersect_key($a, $b);   // Intersection
$diff = array_diff_key($a, $b);             // Difference
$symDiff = array_diff_key($a, $b) + array_diff_key($b, $a); // Symmetric difference
> **Запомни:** HashSet — это когда тебе не нужны значения, только быстрая проверка «есть или нет». Типичные сигналы: «найти дубликат», «обнаружить цикл», «проверить уникальность», «пересечение двух коллекций». Когда можно заменить Set на математику или XOR — делай это для O(1) памяти. В PHP используй `array_flip()` для создания Set из массива и `isset()` для O(1) проверки.

Итоги

  1. HashSet = HashMap без значений, только ключи
  2. O(1) для add, remove, contains
  3. Идеален для: дубликаты, циклы, уникальность, пересечения
  4. В PHP: array_flip() + isset() для O(1) Set-операций
  5. array_intersect_key(), array_diff_key() для множественных операций
  6. Альтернативы: XOR и математика для O(1) памяти

Проверь себя

5 из 8

Какова сложность нахождения пересечения двух множеств A (n элементов) и B (m элементов) через `array_intersect_key()`?

Как в Python получить из списка структуру с O(1) проверкой принадлежности?

В задаче Valid Sudoku для вычисления индекса бокса 3x3 используется формула `intdiv($i, 3) * 3 + intdiv($j, 3)`. Какой boxIdx для ячейки (4, 7)?

Как в C# получить из массива структуру с O(1) проверкой принадлежности?

Что вернёт `singleNumberXor([5, 3, 5, 3, 7])`?