Условие

Дан массив целых чисел nums длиной 2 * n, содержащий n + 1 уникальных элементов, один из которых повторяется ровно n раз. Требуется вернуть элемент, который повторяется n раз.

Примеры

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

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

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

Решение

fun repeatedNTimes(nums: IntArray): Int {
    val seen = mutableSetOf<Int>()
    for (num in nums) {
        // Если число уже встречалось, значит это искомый элемент
        if (!seen.add(num)) {
            return num
        }
    }
    // По условию задачи, такой элемент всегда существует, поэтому return -1 не достигнется
    return -1
}

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

O(n), где n — длина массива nums, поскольку мы проходим по массиву один раз.

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

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