Python-сообщество

Всем привет !

Прошу помочь с решением задачки с яндекс контеста
Перечитал условие раз 5 и так и не понял с чего начать(

Марсоход раз в час записывает в массив информацию о солнечной радиации. Каждое значение — это число от 0 до 100.

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

Исходные массивы могут быть длиной от 2 до 500 элементов.

Например, исходный массив — nums = .

Берём первое значение массива, это 8. Сравниваем это число с остальными: считаем, сколько в массиве есть чисел, меньших, чем выбранное. В этом массиве четыре числа, меньших, чем 8. Создаём массив result, записываем в него 4.

Точно так же проверяем второе значение в исходном массиве, это единица. В исходном массиве нет ни одного числа, меньшего, чем 1. В массив result записываем второе значение: 0.

Проверяем третье значение в массиве nums, это 2. Есть только одно значение, меньшее, чем 2. В массив result записываем третье значение — 1.

Таким же образом проверяем все остальные значения в nums.

В итоге для входного массива получится результирующий массив .

Решить задачу можно любым образом, пусть даже не самым эффективным. Решение за квадратичное время вполне подойдёт.

Если останутся время и силы, попробуйте найти решение с временной сложностью О(n log n), такое тоже есть.

Формат ввода
Массив целых чисел, записанных через пробел, — показатели радиации.

Формат вывода
Массив целых чисел, записанных через пробел, где каждое число — это количество чисел в исходном массиве, меньших, чем рассматриваемое.


Пример ввода и вывода на скрине

Отредактировано Andrew13 (Фев. 8, 2024 02:21:26)

+++

Прикреплённый файлы:
36.GIF (8,9 KБ)

Тут секрет, знаешь, в чём? Если ты хотя бы раз прошёлся по массиву и посчитал эти элементы, то ты за этот проход мог построить структуру всех остальных пройденных элементов в массиве, запомнив их не хаотично, как они лежали изначально, а в каком-то отсортированном виде. Поэтому при втором прохождении ты можешь их искать уже не в хаотичном массиве, а в отсортированной структуре своей. Так ты можешь быстрее получать количество этих искомых элементов.

Отредактировано py.user.next (Фев. 8, 2024 02:29:57)

Действительно, звучит логично