Объяснил два подхода в JavaScript и Ruby
В этом посте я расскажу, как я решил проблему Сортировать массив по четности на LeetCode.
Дан массив A
неотрицательных целых чисел, вернуть массив, состоящий из всех четных элементов A
, за которыми следуют все нечетные элементы A
.
Вы можете вернуть любой массив ответов, удовлетворяющий этому условию.
Example: Input: [3,1,2,4] Output: [2,4,3,1] The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Есть несколько принятых решений этой проблемы, и я поделюсь с вами двумя из них:
Мой первый подход
Вот шаги, которые я предпринял, чтобы прийти к своему первому решению:
- Определите функцию, которая принимает в качестве аргумента массив с именем
A
. - Создайте два пустых массива; один для хранения номеров
even
, а другой - для хранения номеровodd
. - Итерировать по заданному массиву;
A
. - Проверьте, является ли текущий элемент
A
четным или нечетным, выполнив операции модуля (A[i] % 2 === 0
). - Вставьте каждый элемент
A
в соответствующий ему массив: четные элементы в четный массив и нечетные элементы в нечетный массив. - Добавьте элементы нечетного массива к массиву четных элементов и верните его.
Давайте лучше поймем, посмотрев на следующую реализацию в JavaScript:
Данный массив; A
, разделен на два отдельных массива; even
, содержащий все четные числа, и odd
, содержащий все нечетные числа. Затем эти два массива объединяются таким образом, что за четными элементами следуют нечетные.
Сложность времени и пространства
Каждый элемент данного массива необходимо проверять независимо от того, что происходит, поэтому временная сложность этого решения составляет O (n), где n
- длина A
. Введение новых массивов для хранения четных и нечетных чисел приводит к лишнему пространству, поэтому сложность пространства также равна O (n), но это можно сделать за O (1) сложность пространства без использования лишнего пространства, как вы увидите в следующей части.
Мой второй подход
Это решение немного сложнее по сравнению с моим первым решением, но не требует дополнительного места для хранения чего-либо. Для этого подхода я предприму следующие шаги:
- Создайте индекс
j
и установите для него0
. - Прокрутите данный массив;
A
. - Если вы встретили четный элемент, поменяйте местами этот элемент
A
и элемент индексаj
. - Увеличьте
j
на1
. - Продолжайте до конца
A
, а затем верните массив.
Вот реализация кода на JavaScript:
Метод двух указателей, когда оба указателя начинаются с начала массива, используется в моем втором подходе для выполнения сортировки на месте, и это решение больше не требует пространственной сложности O (n).
Если элемент массива не четный, мы увеличиваем только один указатель; i
. Если он четный, мы меняем местами нечетный и четный элемент, а затем увеличиваем оба указателя j
и i
. Этот процесс меняет местами элементы, если они не на месте, пока все четные элементы в A
не появятся перед всеми нечетными элементами A
.
Сложность времени и пространства
Сложность пространства дополнительно оптимизируется с O (n) до O (1) путем написания решения на месте. Временная сложность этого решения по-прежнему равна O (n), как и первое, где n
- длина A
.
Бонус!
Обычно мне нравится решать одну и ту же проблему на разных языках, и вот как я решил эту проблему в Ruby, используя подход, аналогичный моему первому решению:
Вывод
Объявление новых массивов и итерация по заданному массиву для сохранения его четных и нечетных элементов в их новых соответствующих массивах - простой способ решить эту проблему, но этот первый подход требует дополнительной пространственной сложности O (n). Во второй части проблема решается в пространстве сложности O (1) вместо O (n), поддерживая два указателя для выполнения сортировки на месте.
Надеюсь, эта статья поможет вам найти способ решить этот общий алгоритм, спасибо за чтение!