Условие

Дан отсортированный массив arr. Нужно найти элемент, который встречается более чем в 25% случаев. Гарантируется, что такой элемент существует.

Примеры

Input: [1,2,2,6,6,6,6,7,10] Output: 6

Input: arr = [1,1] Output: 1

Решение

fun findSpecialInteger(arr: IntArray): Int {
    val threshold = arr.size / 4

    var count = 1
    for (i in 1 until arr.size) {
        if (arr[i] == arr[i - 1]) {
            count++
            if (count > threshold) return arr[i]
        } else {
            count = 1
        }
    }
    return arr[0] // Гарантируется, что элемент существует
}

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

O(n), где n — длина массива arr.

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

O(1), так как используются только переменные.