Условие

Дан массив nums длины n, содержащий числа от 1 до n. В массиве есть одно повторяющееся число и одно пропущенное. Найдите и верните эти два числа в виде массива [duplicate, missing].

Примеры

Input: nums = [1, 2, 2, 4] Output: [2, 3]

Input: nums = [1, 1] Output: [1, 2]

Решение

fun findErrorNums(nums: IntArray): IntArray {
    val n = nums.size
    val count = IntArray(n + 1) // Массив для подсчета частот чисел
    var duplicate = -1
    var missing = -1

    // Подсчитываем частоту каждого числа
    for (num in nums) {
        count[num]++
    }

    // Ищем повторяющееся и пропущенное числа
    for (i in 1..n) {
        when (count[i]) {
            2 -> duplicate = i // Число встречается дважды
            0 -> missing = i // Число отсутствует
        }
    }

    return intArrayOf(duplicate, missing)
}

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

O(n), где n — длина массива, так как массив перебирается дважды.

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

O(n), для хранения массива частот.