Find All Numbers Disappeared in an Array

Условие

Дан массив чисел nums длины n, где числа находятся в диапазоне от 1 до n. Некоторые числа могут отсутствовать, а некоторые могут повторяться. Нужно найти все числа в диапазоне 1 до n, которые отсутствуют в массиве.

Примеры

Input: nums = [4,3,2,7,8,2,3,1]

Output: [5,6]

Input: nums = [1,1]

Output: [2]

Решение

fun findDisappearedNumbers(nums: IntArray): List<Int> {
    // Помечаем каждое число, изменяя знак на отрицательный у индекса, соответствующего числу
    for (num in nums) {
        val index = kotlin.math.abs(num) - 1
        if (nums[index] > 0) {
            nums[index] = -nums[index]
        }
    }

    val result = mutableListOf<Int>()
    
    // Индексы, значения которых остались положительными, указывают на отсутствующие числа
    for (i in nums.indices) {
        if (nums[i] > 0) {
            result.add(i + 1)
        }
    }

    return result
}

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

O(n), так как мы проходим по массиву дважды — один раз для пометки чисел и один раз для поиска положительных значений.

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

O(1), если не учитывать результат, так как все изменения происходят внутри массива nums.