350. Intersection of Two Arrays II

Задача

Даны два целочисленных массива nums1 и nums2 , верните массив их пересечения. Каждый элемент в результате должен появиться столько раз, сколько он встречается в обоих массивах, и вы можете вернуть результат в любом порядке.

Примеры

Пример 1

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Пример 2

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Пояснение

[9,4] также принимается.

Решение

Решение

// Временная сложность: O(N + M) — линейная
// Пространственная сложность: O(N) — память зависит только от размера nums1
 
var intersect = function(nums1, nums2) {
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1); // Рекурсивно меняем местами, чтобы nums1 всегда был меньше
    }
 
    const map = {};
 
    // Создаем частотную карту для ПЕРВОГО массива
    // Временная: O(N), где N = nums1.length
    // Пространственная: O(N) (в худшем случае храним все элементы nums1)
    for (const num of nums1) {
        map[num] = (map[num] || 0) + 1;
    }
 
    const result = [];
 
    // Проходим по ВТОРОМУ массиву
    // Временная: O(M), где M = nums2.length
    for (const num of nums2) {
        // Проверка наличия в хеше — в среднем O(1)
        if (map[num] > 0) {
            result.push(num);
            map[num]--; // Уменьшаем счетчик
        }
    }
 
    return result;
};

Решение 2 (мое)

// Временная сложность: O(N + M) — линейная, проходим оба массива
// Пространственная сложность: O(N + M) — храним уникальные элементы из ОБОИХ массивов
 
var intersect = function(nums1, nums2) {
    // В худшем случае здесь будут все уникальные числа из nums1 и nums2
    const cache = {};
    let left = 0;
    let right = 0;
 
    // Временная сложность цикла: O(N + M)
    // N = nums1.length, M = nums2.length
    while (left < nums1.length || right < nums2.length) {
        const digitLeft = nums1[left];
        const digitRight = nums2[right];
 
        if (digitLeft !== undefined) {
            // Если ключа нет, создаем массив [count1, count2]
            if (!cache[digitLeft]) cache[digitLeft] = [0, 0];
            cache[digitLeft][0]++;
            left++;
        }
 
        if (digitRight !== undefined) {
            if (!cache[digitRight]) cache[digitRight] = [0, 0];
            cache[digitRight][1]++;
            right++;
        }
    }
 
    // Временная сложность reduce: O(U + K), 
    // где U — кол-во уникальных ключей (до N+M), 
    // K — размер итогового массива (выходные данные)
    return Object.keys(cache).reduce((acc, digit) => {
        const times = Math.min(...cache[digit]); // O(1), массив всегда из 2 элементов
 
        if (times > 0) {
            // Создание и разворачивание массива зависит от кол-ва совпадений
            const arr = Array.from({
                length: times
            }).fill(+digit);
            acc.push(...arr);
        }
        return acc;
    }, [])
};

Решение 3 (если массивы отсортированы)

// Временная сложность: O(N + M) — проходим каждый массив максимум один раз
// Пространственная сложность: O(1) — не используем дополнительную память для хранения данных
 
var intersect = function(nums1, nums2) {
    let i = 0;
    let j = 0;
    const result = [];
 
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            // Совпадение найдено
            result.push(nums1[i]);
            i++;
            j++;
        }
    }
 
    return result;
};

Решение 4 (если один массив маленький, а второй огромный)

/**
 * @param {number[]} nums1 (Маленький массив)
 * @param {number[]} nums2 (Огромный массив)
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    // Гарантируем, что nums1 - это маленький массив, чтобы бежать по нему
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1);
    }
 
    // ==========================================
    // СЦЕНАРИЙ 1: Массивы НЕ отсортированы
    // ==========================================
    // Временная сложность: O(M * log M)
    //   - Сортировка nums1: O(N * log N)
    //   - Сортировка nums2: O(M * log M) <--- Самая тяжелая операция, которая всё замедляет
    //   - Поиск: O(N * log M)
    //   - Итог определяется сортировкой большого массива.
 
    // Пространственная сложность: O(log M) или O(M) 
    //   - Зависит от реализации sort() в движке JS (стек рекурсии).
 
    // nums1.sort((a, b) => a - b); 
    // nums2.sort((a, b) => a - b);
 
    // ==========================================
    // СЦЕНАРИЙ 2: Массивы УЖЕ отсортированы (входные данные)
    // ==========================================
    // Временная сложность: O(N * log M)
    //   - Мы проходим по маленькому массиву (N раз).
    //   - Внутри делаем бинарный поиск по большому (log M).
    //   - Это ОЧЕНЬ быстро, если N мал, а M огромен.
 
    // Пространственная сложность: O(1)
    //   - Мы не создаем хеш-таблиц, используем только пару переменных-указателей.
 
    const result = [];
    let lowerBound = 0; // Граница поиска в большом массиве
 
    for (let i = 0; i < nums1.length; i++) {
        const target = nums1[i];
 
        // Ищем target в nums2, начиная с индекса lowerBound
        // binarySearch возвращает индекс первого вхождения или -1
        const index = binarySearch(nums2, lowerBound, nums2.length - 1, target);
 
        if (index !== -1) {
            result.push(target);
            // Важно! В следующий раз ищем СТРОГО после найденного элемента,
            // чтобы не использовать одну и ту же цифру из nums2 дважды.
            lowerBound = index + 1;
        }
    }
 
    return result;
};
 
// Хелпер: Бинарный поиск первого вхождения (Lower Bound)
function binarySearch(arr, left, right, target) {
    let resultIndex = -1;
 
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
 
        if (arr[mid] === target) {
            resultIndex = mid;
            right = mid - 1; // Продолжаем искать слева, чтобы найти ПЕРВОЕ вхождение
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
 
    return resultIndex;
}