Intersection of Two Arrays II

Условие

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

Примеры

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

Output: [2, 2]

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

Output: [4, 9]

Explanation: Результат может быть в любом порядке: [9,4] также является допустимым ответом.

Решение

fun intersect(nums1: IntArray, nums2: IntArray): IntArray {
    val map = mutableMapOf<Int, Int>()  // Словарь для хранения количества каждого элемента в nums1
    val result = mutableListOf<Int>()  // Список для хранения результата

    // Подсчитываем количество каждого элемента в nums1
    for (num in nums1) {
        map[num] = map.getOrDefault(num, 0) + 1
    }

    // Проходим по nums2 и добавляем общие элементы в результат
    for (num in nums2) {
        if (map.containsKey(num) && map[num]!! > 0) {
            result.add(num)  // Добавляем элемент в результат
            map[num] = map[num]!! - 1  // Уменьшаем счетчик для элемента
        }
    }

    // Преобразуем результат в массив и возвращаем
    return result.toIntArray()
}

Временная сложность

O(n + m), где n — длина nums1, а m — длина nums2, так как мы проходим по каждому массиву один раз.

Пространственная сложность

O(min(n, m)), так как в худшем случае результат содержит все элементы из меньшего массива.