Задача 9

Условия задачи:

У вас есть массив an_array, состоящий из неотрицательных целых чисел. Верните массив, в котором все нечетные элементы массива an_array следуют за всеми четными элементами  an_array.

п.с. Это массовая задача, встречается очень часто, точно видел ее на codewar

Решение задачи:

#1
def segregate_even_odd(an_array):
    # Указатель на начало (для четных)
    left = 0
    # Указатель на конец (для нечетных)
    right = len(an_array) - 1

    while left < right:
        # Ищем первый нечетный элемент слева
        while left < right and an_array[left] % 2 == 0:
            left += 1
        # Ищем первый четный элемент справа
        while left < right and an_array[right] % 2 != 0:
            right -= 1
        # Меняем местами
        if left < right:
            an_array[left], an_array[right] = an_array[right], an_array[left]
            left += 1
            right -= 1

    return an_array

Как это работает?

1. Два указателя:

   • left начинает с начала массива и движется вправо, пока не найдет нечетный элемент.

   • right начинает с конца массива и движется влево, пока не найдет четный элемент.

2. Обмен:

   • Когда оба указателя нашли "неправильные" элементы, они меняются местами.

   • Процесс повторяется, пока left не дойдет до right.

3. Результат:

   • Все четные числа оказываются в первой половине массива.

   • Все нечетные — во второй половине.

Сложность:

• Время: O(n) — каждый элемент обрабатывается максимум один раз.

• Память: O(1) — алгоритм работает на месте, без дополнительных структур данных.

Другие варианты:

1. Через два списка (четные + нечетные):

    

   def segregate_even_odd(an_array):
       even = [x for x in an_array if x % 2 == 0]
       odd = [x for x in an_array if x % 2 != 0]
       return even + odd

   • Плюсы: Простота.

   • Минусы: Требует O(n) дополнительной памяти.

2. Сортировка с ключом:

    

   def segregate_even_odd(an_array):
       return sorted(an_array, key=lambda x: x % 2 != 0)

   • Плюсы: Лаконично.

   • Минусы: Сложность O(n log n) из-за сортировки.