PrepBro
← Назад к вопросам

Продукт массива кроме себя

2.0 Middle🔥 161 комментариев
#Python Core

Условие

Дан массив чисел. Верните массив, где каждый элемент — это произведение всех остальных элементов исходного массива.

Ограничения: нельзя использовать деление, O(n) по времени.

Пример

product_except_self([1, 2, 3, 4]) → [24, 12, 8, 6] product_except_self([-1, 1, 0, -3, 3]) → [0, 0, 9, 0, 0]

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Продукт массива кроме себя

Это классическая задача на префиксы и суффиксы. Ключевая идея: для каждой позиции i результат = произведение всех элементов слева × произведение всех элементов справа.

Подход: Два прохода

Вместо того чтобы считать произведение всех элементов и делить (что запрещено), мы:

  1. Первый проход слева направо — считаем произведение всех элементов слева
  2. Второй проход справа налево — умножаем на произведение элементов справа

Визуализация

Массив: [1, 2, 3, 4]

Шаг 1: Произведение слева
Для индекса i = произведение [0...i-1]

position:  0  1   2    3
product:   1  1   1*2  1*2*3
left:    [ 1, 1,  2,   6  ]

Шаг 2: Произведение справа
Для индекса i = произведение [i+1...n-1]

right:   [ 24, 12, 4,  1  ]

Шаг 3: Результат = левое[i] * правое[i]
result: [1*24, 1*12, 2*4, 6*1]
result: [24, 12, 8, 6]

Реализация (O(n) время, O(1) доп. память)

def product_except_self(nums):
    """
    Для каждого элемента вычисляет произведение всех остальных.
    
    Сложность: O(n) время, O(1) доп. память (не считая результата)
    Метод: Префикс и суффикс
    """
    n = len(nums)
    result = [1] * n
    
    # Шаг 1: Считаем произведение всех элементов слева
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Шаг 2: Считаем произведение элементов справа и умножаем
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

Пошаговое выполнение

Входные данные: [1, 2, 3, 4]

Шаг 1: Слева направо (prefix)
  i=0: result[0] = 1 (prefix=1), prefix = 1*1 = 1
  i=1: result[1] = 1 (prefix=1), prefix = 1*2 = 2
  i=2: result[2] = 2 (prefix=2), prefix = 2*3 = 6
  i=3: result[3] = 6 (prefix=6), prefix = 6*4 = 24
  result = [1, 1, 2, 6]

Шаг 2: Справа налево (suffix)
  i=3: result[3] *= 1 (suffix=1) → 6*1=6, suffix = 1*4 = 4
  i=2: result[2] *= 4 (suffix=4) → 2*4=8, suffix = 4*3 = 12
  i=1: result[1] *= 12 (suffix=12) → 1*12=12, suffix = 12*2 = 24
  i=0: result[0] *= 24 (suffix=24) → 1*24=24, suffix = 24*1 = 24
  result = [24, 12, 8, 6]

Результат: [24, 12, 8, 6] ✓

С нулями и отрицательными числами

def product_except_self_detailed(nums):
    n = len(nums)
    result = [1] * n
    
    # Левые произведения
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    
    # Правые произведения
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

# Примеры
print(product_except_self_detailed([1, 2, 3, 4]))  # [24, 12, 8, 6]
print(product_except_self_detailed([2, 3, 4, 5]))  # [60, 40, 30, 24]
print(product_except_self_detailed([-1, 1, 0, -3, 3]))  # [0, 0, 9, 0, 0]

Для [-1, 1, 0, -3, 3]:

Шаг 1 (prefix слева):
result = [1, -1, -1, 0, 0]  (произведение всего слева)

Шаг 2 (suffix справа):
result[4] = 0 * 1 = 0 ← есть 0 слева
result[3] = 0 * (-3) = 0 ← есть 0 слева
result[2] = (-1)*(-3)*3 = 9 ← нет нуля в других элементах
result[1] = (-1) * (-3*3) = (-1)*(-9) = 9... нет, не правильно

Актуально:
result[2] = (-1)*1 умножить на (3*(-3)) = (-1)*(-9) = 9
Итоговый результат: [0, 0, 9, 0, 0]

Наивный подход (с делением — запрещён)

def product_except_self_naive(nums):
    """
    ❌ Этот подход ЗАПРЕЩЁН в задаче из-за требования без деления
    """
    total_product = 1
    zero_count = 0
    zero_index = -1
    
    for i, num in enumerate(nums):
        if num == 0:
            zero_count += 1
            zero_index = i
        else:
            total_product *= num
    
    result = [0] * len(nums)
    
    if zero_count > 1:
        return result  # Больше одного нуля → все нули
    
    if zero_count == 1:
        result[zero_index] = total_product
        return result
    
    # Нет нулей
    for i in range(len(nums)):
        result[i] = total_product // nums[i]  # ← Деление запрещено!
    
    return result

Оптимизация памяти

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

def product_except_self_optimized(nums):
    n = len(nums)
    result = [1] * n
    
    # Префиксы в result
    for i in range(1, n):
        result[i] = result[i - 1] * nums[i - 1]
    
    # Суффиксы и финальное умножение
    suffix = 1
    for i in range(n - 1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    
    return result

Это работает в O(n) времени и O(1) дополнительной памяти (если не считать результирующий массив).

Тестирование

def test_product_except_self():
    # Базовые случаи
    assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
    assert product_except_self([2, 3, 4, 5]) == [60, 40, 30, 24]
    
    # С нулями
    assert product_except_self([0, 0]) == [0, 0]
    assert product_except_self([1, 0, 3, 4]) == [0, 12, 0, 0]
    
    # С отрицательными
    assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
    assert product_except_self([-1, -2, -3]) == [-6, -3, -2]
    
    # Один элемент (не стандартный случай, но проверим)
    assert product_except_self([5]) == [1]
    
    print("Все тесты пройдены!")

test_product_except_self()

Ключевая идея этой задачи: нужно думать о массиве как о произведении левой и правой частей, а не как о целом произведении.

Продукт массива кроме себя | PrepBro