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

Решение: Произведение массива кроме себя

Подход к решению

Эта задача требует вычисления произведения всех элементов, кроме текущего, без использования операции деления. Оптимальное решение использует два прохода по массиву: один слева направо, второй справа налево, накапливая произведения префиксов и суффиксов.

Алгоритм

1. Левые произведения — для каждой позиции i вычисляем произведение всех элементов слева от неё
2. Правые произведения — для каждой позиции i вычисляем произведение всех элементов справа от неё
3. Результат — для каждой позиции результат = (произведение слева) × (произведение справа)

Реализация на Python

def productExceptSelf(nums):
    """
    Вычислить произведение всех элементов кроме себя.
    Без использования деления!
    
    Args:
        nums: List[int] - массив целых чисел (может содержать нули)
    
    Returns:
        List[int] - массив произведений
    """
    n = len(nums)
    result = [1] * n
    
    # Первый проход: накапливаем произведение слева
    # result[i] будет содержать произведение всех элементов ДО позиции i
    left_product = 1
    for i in range(n):
        result[i] = left_product
        left_product *= nums[i]
    
    # Второй проход: умножаем на произведение справа
    # result[i] *= произведение всех элементов ПОСЛЕ позиции i
    right_product = 1
    for i in range(n - 1, -1, -1):
        result[i] *= right_product
        right_product *= nums[i]
    
    return result

Трассировка алгоритма

Для массива [1, 2, 3, 4]:

После левого прохода:

result = [1, 1, 2, 6]
  i=0: result[0] = 1,            left_product = 1*1 = 1
  i=1: result[1] = 1,            left_product = 1*2 = 2
  i=2: result[2] = 2,            left_product = 2*3 = 6
  i=3: result[3] = 6,            left_product = 6*4 = 24

После правого прохода:

result = [24, 12, 8, 6]
  i=3: result[3] = 6 * 1 = 6,    right_product = 1*4 = 4
  i=2: result[2] = 2 * 4 = 8,    right_product = 4*3 = 12
  i=1: result[1] = 1 * 12 = 12,  right_product = 12*2 = 24
  i=0: result[0] = 1 * 24 = 24,  right_product = 24*1 = 24

Примеры использования

# Пример 1: Базовый случай
result = productExceptSelf([1, 2, 3, 4])
print(result)  # [24, 12, 8, 6]

# Пример 2: С нулем
result = productExceptSelf([0, 1, 2, 3])
print(result)  # [6, 0, 0, 0]

# Пример 3: Два нуля
result = productExceptSelf([0, 0, 1, 2])
print(result)  # [0, 0, 0, 0]

# Пример 4: Отрицательные числа
result = productExceptSelf([-1, 0, 1, 2])
print(result)  # [0, -2, 0, 0]

# Пример 5: Один элемент
result = productExceptSelf([5])
print(result)  # [1]

Анализ сложности

• Временная сложность: O(n) — два линейных прохода по массиву
• Пространственная сложность: O(1) — только результирующий массив, используемый результат не считается дополнительным местом

Ключевые особенности

1. Без деления — прямое требование задачи, раньше студенты часто использовали деление и потом исключали нули
2. Обработка нулей — алгоритм автоматически правильно обрабатывает случаи с нулями
3. Эффективность — линейное время, что является оптимальным (нельзя быстрее)
4. In-place — используем результирующий массив как вспомогательное место

Сравнение подходов

Это классическая задача на собеседованиях для проверки понимания сложности алгоритмов и умения оптимизировать решения.