Условие

Дан массив heights, где heights[i] — рост i-го ученика в классе.

Ученики должны стоять в порядке неубывания роста.

Верните количество учеников, стоящих не на своём месте.

Примеры

Input: heights = [1,1,4,2,1,3] Output: 3 Explanation: Ожидаемый порядок: [1,1,1,2,3,4]. Неверно стоят heights[2] = 4, heights[4] = 1, heights[5] = 3.

Input: heights = [5,1,2,3,4] Output: 5 Explanation: Ожидаемый порядок: [1,2,3,4,5]. Все ученики стоят не на своём месте.

Input: heights = [1,2,3,4,5] Output: 0 Explanation: Все ученики уже стоят правильно.

Решение

fun heightChecker(heights: IntArray): Int {
    // Подсчитываем количество каждого роста
    val count = IntArray(101)
    for (h in heights) {
        count[h]++
    }

    var index = 0
    var result = 0

    // Восстанавливаем отсортированный массив и сравниваем с оригиналом
    for (h in count.indices) {
        while (count[h] > 0) {
            if (heights[index] != h) result++
            index++
            count[h]--
        }
    }

    return result
}

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

O(n), так как используем сортировку подсчётом.

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

O(1), так как дополнительный массив фиксированного размера (101).