Intersection of Two Arrays

Условие

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

Примеры

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

Output: [2]

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

Output: [9, 4]

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

Решение

fun intersection(nums1: IntArray, nums2: IntArray): IntArray {
    val result = mutableListOf<Int>()  // Создаем список для хранения результата
    val uniqueNums1 = mutableSetOf<Int>()  // Множество для хранения уникальных элементов из nums1

    // Заполняем множество уникальными значениями из nums1
    for (num in nums1) {
        uniqueNums1.add(num)
    }

    // Проверяем, какие элементы из nums2 присутствуют в uniqueNums1 и добавляем их в результат
    for (num in nums2) {
        if (uniqueNums1.contains(num)) {
            result.add(num)  // Добавляем элемент в результат
            uniqueNums1.remove(num)  // Удаляем из множества, чтобы избежать дубликатов
        }
    }

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

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

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

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

O(n), так как требуется множество для хранения уникальных элементов из nums1.