Premium

Сортировка

Проверка роста

Посчитать, сколько элементов стоят не на своих местах

Легкий

Постановка задачи

Описание (LeetCode - 1051. Height Checker)

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

Ученики должны стоять в неубывающем порядке по росту. Нужно вернуть количество индексов, где текущий порядок отличается от ожидаемого.

Пример 1:

heights = [1, 1, 4, 2, 1, 3]

Результат:

3

Пояснение:

Ожидаемый порядок:

[1, 1, 1, 2, 3, 4]

Ученики с индексами 2, 4 и 5 не на своих местах.

Пример 2:

heights = [5, 1, 2, 3, 4]

Результат:

5

Ограничения:

  • 1 <= heights.length <= 100
  • 1 <= heights[i] <= 100

Решение

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

Идея решения:

Создадим копию массива heights, назовем копию expected и отсортируем. После этого пройдем по индексам и посчитаем, сколько раз heights[i] отличается от expected[i].

Почему это корректно? Отсортированная копия показывает ожидаемую последовательность ростов. Если на позиции i стоит другое значение, значит ученик на этой позиции находится не там, где должен.

Основные шаги:

  1. Создаем копию массива heights.
  2. Сортируем копию по возрастанию.
  3. Идем по всем индексам.
  4. Если heights[i] != expected[i], увеличиваем счетчик.
  5. Возвращаем счетчик.

Рассмотрим пример:

heights = [1, 1, 4, 2, 1, 3]

После сортировки:

expected = [1, 1, 1, 2, 3, 4]

Сравниваем по индексам:

  1. 0: 1 == 1, все хорошо.
  2. 1: 1 == 1, все хорошо.
  3. 2: 4 != 1, не на своем месте.
  4. 3: 2 == 2, все хорошо.
  5. 4: 1 != 3, не на своем месте.
  6. 5: 3 != 4, не на своем месте.

Итоговый ответ равен 3.

В этой задаче ограничения маленькие, а значения ростов лежат в диапазоне от 1 до 100. Можно решить ее через подсчет частот за O(n + 100) или через сортировку подсчетом. Но обычная сортировка проще и лучше показывает сам паттерн.

Оценка сложности

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

Сортировка массива длины n занимает O(n * log n). Дополнительный проход для сравнения занимает O(n).

Итоговая временная сложность: O(n * log n).

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

Мы создаем копию массива длины n, поэтому дополнительная память равна O(n).

Код решения

Приведем код решения.

func heightChecker(heights []int) int {
    expected := []int{}
    expected = append(expected, heights...)
    sort.Ints(expected)
    count := 0
    for i := range heights {
        if heights[i] != expected[i] {
            count++
        }
    }
    return count
}

Итоги

Главная идея задачи: если нужно сравнить текущий порядок с правильным, мы можем получить правильный порядок сортировкой. После этого задача сводится к простому линейному сравнению двух массивов.

Войдите чтобы отмечать прогресс