Majority Element

Условие

Дан массив nums размера n. Нужно найти элемент, который встречается более чем n/2 раз, т.е. большинство элементов. Гарантируется, что такой элемент существует.

Примеры

Input: nums = [3, 2, 3]

Output: 3

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

Output: 2

Решение

fun majorityElement(nums: IntArray): Int {
    // Введем переменные для хранения возможного кандидата и его счетчика
    var candidate = nums[0]
    var count = 0
    
    // Используем алгоритм Boyer-Moore для поиска большинства
    for (num in nums) {
        if (count == 0) {
            candidate = num // Обновляем кандидата, если счетчик обнулен
        }
        count += if (num == candidate) 1 else -1 // Увеличиваем или уменьшаем счетчик
    }
    
    return candidate // Возвращаем кандидата, который станет большинством
}

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

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

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

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