Как написать функцию для нахождения числа первого массива которого нет во втором

«Как написать функцию для нахождения числа первого массива которого нет во втором» — вопрос из категории Алгоритмы и структуры данных, который задают на 23% собеседований Android Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

fun findMissingNumber(first: IntArray, second: IntArray): Int? {
    val secondSet = second.toHashSet()
    return first.firstOrNull { it !in secondSet }
}

Эта функция:

  1. Создает HashSet из второго массива для быстрого поиска (O(1))
  2. Ищет первый элемент первого массива, которого нет в HashSet
  3. Возвращает null если все элементы первого массива есть во втором

Пример использования:

val arr1 = intArrayOf(1, 2, 3, 4)
val arr2 = intArrayOf(4, 2, 1)
println(findMissingNumber(arr1, arr2)) // Выведет 3

Сложность: O(n+m), где n и m - размеры массивов