Объяснил два подхода в 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.

Есть несколько принятых решений этой проблемы, и я поделюсь с вами двумя из них:

Мой первый подход

Вот шаги, которые я предпринял, чтобы прийти к своему первому решению:

  1. Определите функцию, которая принимает в качестве аргумента массив с именем A.
  2. Создайте два пустых массива; один для хранения номеров even, а другой - для хранения номеров odd.
  3. Итерировать по заданному массиву; A.
  4. Проверьте, является ли текущий элемент A четным или нечетным, выполнив операции модуля (A[i] % 2 === 0).
  5. Вставьте каждый элемент A в соответствующий ему массив: четные элементы в четный массив и нечетные элементы в нечетный массив.
  6. Добавьте элементы нечетного массива к массиву четных элементов и верните его.

Давайте лучше поймем, посмотрев на следующую реализацию в JavaScript:

Данный массив; A, разделен на два отдельных массива; even, содержащий все четные числа, и odd, содержащий все нечетные числа. Затем эти два массива объединяются таким образом, что за четными элементами следуют нечетные.

Сложность времени и пространства

Каждый элемент данного массива необходимо проверять независимо от того, что происходит, поэтому временная сложность этого решения составляет O (n), где n - длина A. Введение новых массивов для хранения четных и нечетных чисел приводит к лишнему пространству, поэтому сложность пространства также равна O (n), но это можно сделать за O (1) сложность пространства без использования лишнего пространства, как вы увидите в следующей части.

Мой второй подход

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

  1. Создайте индекс j и установите для него 0.
  2. Прокрутите данный массив; A.
  3. Если вы встретили четный элемент, поменяйте местами этот элемент A и элемент индекса j.
  4. Увеличьте j на 1.
  5. Продолжайте до конца A, а затем верните массив.

Вот реализация кода на JavaScript:

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

Если элемент массива не четный, мы увеличиваем только один указатель; i. Если он четный, мы меняем местами нечетный и четный элемент, а затем увеличиваем оба указателя j и i. Этот процесс меняет местами элементы, если они не на месте, пока все четные элементы в A не появятся перед всеми нечетными элементами A.

Сложность времени и пространства

Сложность пространства дополнительно оптимизируется с O (n) до O (1) путем написания решения на месте. Временная сложность этого решения по-прежнему равна O (n), как и первое, где n - длина A.

Бонус!

Обычно мне нравится решать одну и ту же проблему на разных языках, и вот как я решил эту проблему в Ruby, используя подход, аналогичный моему первому решению:

Вывод

Объявление новых массивов и итерация по заданному массиву для сохранения его четных и нечетных элементов в их новых соответствующих массивах - простой способ решить эту проблему, но этот первый подход требует дополнительной пространственной сложности O (n). Во второй части проблема решается в пространстве сложности O (1) вместо O (n), поддерживая два указателя для выполнения сортировки на месте.

Надеюсь, эта статья поможет вам найти способ решить этот общий алгоритм, спасибо за чтение!

Подробнее об алгоритме: