e-olymp 8963. Наименьшие влево

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

Входные данные

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

Выходные данные

Выведите элементы обновленного массива.

Тесты

Ввод Вывод
1 7
6 -3 -7 4 -7 -4 5
-7 -7 6 -3 4 -4 5
2 2
100 -100
-100 100
3 6
-2 -2 7 3 99 -2
-2 -2 -2 7 3 99
4 5
1 1 1 1 1
1 1 1 1 1

Решение

Вместо обычных массивов будем использовать векторы, чтобы было удобнее добавлять элементы в конец. Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент вектора меньше min, то min присваивается значение этого элемента, и так пока не найдено наименьшее число. Подсчитаем, сколько раз оно встречается в векторе. Столько же раз его нужно добавить в новый вектор. Наконец, переносим в v2 все оставшиеся элементы, не равные min.

Код программы

Ссылки

решение на E-olymp
код на ideone

2 thoughts on “e-olymp 8963. Наименьшие влево

    • Нужно сделать правильные отступы.
    • Вместо ссылки на ideone стоит ссылка на текущую страницу.
    • Когда в пояснении Вы пишите про min, Вы ведь имеете в виду переменную из кода? Тогда почему размечаете её как математическую формулу?
    • Ну и самое главное — алгоритм плохой. Он правильный. И задачу решает. Но плохой. Вложенные циклы в нем выполняют слишком много операций. Вы просматриваете массив и опускаете каждый минимальный элемент на одну позицию вниз. Хотя заранее знаете где должны оказаться все минимальные элементы. Даже если на вход программы дать массив в котором минимальный элемент один и он уже стоит слева, программа будет $n$ раз просматривать $n$ элементов, сравнивая их с минимальным. Другими словами, Ваш алгоритм выполняет порядка $O\left(n^2\right)$ операций. А нужно $O\left(n\right)$. Конечно, при таких маленьких массивах мы эффекта не увидим, но для больших данных разница будет огромной.
  1. Да. Такой вариант мне больше нравится. Если еще и размер (capacity) поставить сразу по числу элементов, то решение будет иметь линейную сложность. Хотя, все это «из пушки по воробьям» — два вектора вместо одного массива.
    Задача легко решается без всяких трюков и сложных структур данных:

    В строках 10-12 все минимальные элементы стираются, а в 13-й они добисываются на нужные места в начало.
    Но зачтено и в Вашей версии. С учетом того, что прошлая Ваша попытка фактически реализовала сортировку пузырьком в самой не эффективной версии, даю Вам задачу 2663, которая поможет разобраться с этим алгоритмом. Желаю успехов.

Добавить комментарий