Алгоритмы - LeetCode - Python - Dayli - 2149. Rearrange Array Elements by Sign

Дано: массив целых чисел nums четной длины, состоящий из равного количества положительных и отрицательных целых чисел.

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

- Каждое следующее число имеет противоположный знак.
- Для всех целых чисел с одинаковым знаком сохраняется порядок, в котором они находились в nums.
- Переупорядоченный массив начинается с положительного целого числа.

Пример 1:
Дано: nums = [3,1,-2,-5,2,-4]
Ответ: [3,-2,1,-5,2,-4]

Пример 2:
Дано: nums = [-1,1]
Ответ: [1,-1]

Ограничения:
2 <= nums.length <= 2 * 10^5
длина nums.length четная
1 <= |nums[i]| <= 10^5
nums состоит из одинакового количества положительных и отрицательных целых чисел.

Решение:

class Solution:
def rearrangeArray(self, nums: List[int]) -> List[int]:
rearranged = [0] * len(nums)
positive_index, negative_index = 0, 1
for num in nums:
if num > 0:
rearranged[positive_index] = num
positive_index += 2
else:
rearranged[negative_index] = num
negative_index += 2
return rearranged

ИДЕЯ: создаём новый пустой массив, в котором упорядочим значения из исходного.

Присвоим первичные индексы для положительного и отрицательного чисел:

так как по условию первое число должно быть положительным, то оно получит индекс 0, а отрицательное индекс 1.

Начинаем перебор по исходному массиву:

если число положительное по вставляем их в индексы 0 + 2: 0, 2, 4, 6 и тд

если число отрицательное, то вставляем их в индексы, 1+ 2: 1,3,5,7 и тд

заполнение первых 4 значений для списка [1,2,3,4,-1,-2,-3,-4,1,-1]

Временная сложность: цикл даёт O(n)

Пространственная сложность: новый массив даёт O(n)