UniLecs #148_1. Обработка массива
UniLecsЗадача: дан массив целых чисел. Необходимо сдвинуть нулевые элементы в конец массива, сохранив при этом относительный порядок ненулувых элементов.
Входные данные: arr - массив целых чисел, размер массива от 1 до 10^3.
Элементы массива по модулю от 1 до 10^3.
Вывод: преобразовать массив таким образом, чтобы все нулевые элементы оказались в конце массива, а относит.порядок ненулевых элементов сохранился.
Условие: использовать для преобразования исходный массив без использования доп. O(n) памяти, где n - размер исх.массива.
Пример:
- arr = [0, 0, -5, 4, 0, 2, 0]; Answer: arr = [-5, 4, 2, 0, 0, 0, 0]
- arr = [4, 0, 6, 0, 0, -5]; Answer: arr = [4, 6, -5, 0, 0, 0]
- arr = [1, 2, 3, 4, 5, 6]; Answer: arr = [1, 2, 3, 4, 5, 6]
Реализация:
- Andrew Bystrov, Java: 1 балл
https://gist.github.com/AndrewBystrov/50758be312c431436196a928fae4ad87
2. @voodoo_woodpecker, VBA, Go, JS, R, Rust, Python, C: 1.6 балла
https://gist.github.com/MikePeleah/8febdf161c96505c7158f134de7f79e6
3. @jinxonik, С++, Delphi, GolfScript, Assembler, Python, Ruby: (1 + 4*0.5 + 3*0.1 + 5*0.1) = 3.8 балла
МЕТОД №1: удаление элементов массива (вектора) с добавлением нулей в конец. Перебираем все элементы массива от конца (кроме последнего) к началу и удаляем все нули. В конце восстанавливаем первоначальный размер массива путём добавления нулей в конец.
МЕТОД №2: копирование ненулевых элементов массива (вектора) с добавлением нулей в конец. Чтобы исключить при каждом удалении копирование каждого из последующих элементов на одну позицию влево, будем копировать ненулевые значения в тот же вектор, а остаток вектора заполнять нулями. Самый нормальный метод (вместе с 2А).
МЕТОД №3: использование функции сортировки в двусвязном списке. Значения при сортировке меняются местами, только если второй аргумент равен нулю. Почему работает именно такое условие, а не "если первый аргумент не равен нулю" ? Дело в том, что в методе sort используется устойчивая сортировка (порядок равных элементов сохраняется), а функция сравнения возвращает true, если a < b. Следовательно перемещение элементов производится только при возвращении значения true (иначе нельзя было бы понять, больше ли первый элемент второго [и его нужно переместить вниз] или равен ему [не трогать]). Не самый оптимальный вариант, но самый короткий в записи (гольф) :)
МЕТОД №4: разворачивание подмассивов.
Примем за begin начало массива, а за end его конец. Пока эти два указателя не встретятся (в т.ч. при поиске), повторяем следующие действия. Найдём первый нулевой элемент, начиная с begin (результат запишем в begin) и последний ненулевой, начиная с end (в обратном порядке; результат запишем в end). Развернём элементы массива (переставим в обратном порядке) от begin до end. Снова найдём последний ненулевой элемент (end) и снова развернём элементы от begin до нового end. Увеличим begin на 1 (поскольку он точно не будет указывать на 0). Повторим.
МЕТОД №5: использование функции stable_partition.
В C++ есть функция std::stable_partition, которая упорядочивает элементы таким образом, чтобы все элементы, удовлетворяющие определённому условию шли в начале, а остальные - в конце, сохраняя при этом относительный порядок элементов.
https://gist.github.com/jin-x/3cfd9afe4b31b07af9c2a089303042f5
4. @akolosov364, JS, Rust: 1.6 балла
Метод 1. Проход по исходному массиву с удалением нулей и добавления их в конец массива, при этом необходимо знать сколько нулей добавлено в конец массива, чтобы не произошел бесконечный цикл.
Метод 2. Решение без удаления элементов массива. Проход по исходному массиву с последующим свапом нулевого элемента с каждым следующим элементом до последнего нулевого элемента.
https://gist.github.com/KolosovAO/b1947199dd3b4b7bf0fc8d58379fbf5e
Test Rust: https://repl.it/@AlieksieiKoloso/task148rust?language=rust
Test JS: https://repl.it/@AlieksieiKoloso/task148?language=nodejs
5. Антон, Rust: 1.5 балла
https://gist.github.com/AnthonyMikh/3d6d9f81a91128ba116d7096d57e05e9
Рекурсивный подход:
https://gist.github.com/AnthonyMikh/55540519dc92d1163d89371e24efa8fb
6. @kirillmotrichkin, Python: 1 + 7*0.5 = 4.5 балла
Вариант 1: Сортировка пузырьком с флагом так, чтобы сортировались только нули.
Вариант 2: Будем удалять все элементы из конца массива, если это не ноль - записывать в начало. Нули считаем и дописываем в конце.
Вариант 3: Удалим все нули, а потом вставим их в конец массива
Вариант 4: Для каждого найденного нуля будем брать часть массива до нуля, часть после нуля, склеивать эти два массива и ноль
Вариант 5: Внутренняя устойчивая сортировка в Python, нужно только переопределить ключ
Вариант 6: Рекурсия: если находим ноль, то двигаем его в конец, и запускаем функцию для оставшейся части массива
Вариант 7: Eсли нулей больше, чем остальных чисел, то будем двигать нули
Вариант 8: Нарежем массив на куски без нулей и склеим их сразу и одной строкой кода, для этого определим две функции, которые будут искать края отрезков
https://gist.github.com/superkiria/afc8cc36c3bb0459a6acac740a3404a3
Test: https://repl.it/@superkiria/unilecs148
7. @LostInKadath, C++: 1 балл
Мы просто идем с начала массива и затираем нулевые элементы ближайшими справа ненулевыми. Для этого заводим два итератора, один из которых указывает - на текущий анализируемый элемент, а второй - на место вставки. Если анализируемый элемент не ноль - записываем его на место, указываемое вторым итератором. После того, как проанализировали все элементы - дописываем в конец массива нужное количество нулей. Сложность подхода - в худшем случае 2*O(n). Первый проход на анализ массива, второй - на заполнение нулями.
https://gist.github.com/LostInKadath/e27007552783eb8ad9b4d704121959a4
8. @egormasharskii, C++: 2 балла
Метод 1. Знай и люби стандартную библиотеку языка которым пользуешься ;-) В stl есть замечательный алгоритм remove, который перемещает заданные элементы в конец диапазона, сохраняя порядок других элементов.
Метод 2. Заведем два итератора. Один для чтения, другой для записи. Будем двигать итератор для чтения и если елемент не ноль то скопируем его туда куда указывает итератор записи. Чтобы избежать лишних обменов, проверяем не равны ли итераторы записи и чтения.
Метод 3. Сначала найдем первый нулевой элемент. Если такого нет то можно заканчивать, иначе будем делать то что и в предыдущем алгоритме. Преимущество в том что не надо проверять равенство итераторов чтения и записи.
https://gist.github.com/myegor/0296c2ad58e7f57f872162f676a78537
Test: http://cpp.sh/3o6tm
9. @my_diamonds_dancing, C#, C++, Python: 1.2 балла
C#: https://github.com/myDiamondsDancing/UniLecs-Tasks/blob/master/Task%20148.cs
C++: https://github.com/myDiamondsDancing/UniLecs-Tasks/blob/master/Task%20148.cpp
Python: https://github.com/myDiamondsDancing/UniLecs-Tasks/blob/master/Task%20148.py