Произведение элементов массива кроме текущего: разбор задачи

Почему эта задача важна?

Задача на вычисление произведения элементов позволяет оценить:

• Умение работать с префиксными и суффиксными вычислениями
• Способность оптимизировать пространственную сложность
• Навыки решения задач с ограничениями (без использования деления)
• Понимание техники двух проходов по массиву

Постановка задачи

Формулировка:

Дан массив чисел nums. Нужно вернуть массив output, где output[i] равен произведению всех элементов nums кроме nums[i].

Ограничения:

• Нельзя использовать операцию деления
• Решение должно работать за O(n)
• Произведение гарантированно помещается в 32-битное целое число

Примеры:

// Первый пример
Input: nums = [1, 2, 3, 4]
Output: [24, 12, 8, 6]
// Для 1: 2*3*4 = 24
// Для 2: 1*3*4 = 12
// Для 3: 1*2*4 = 8
// Для 4: 1*2*3 = 6

// Второй пример
Input: nums = [-1, 1, 0, -3, 3]
Output: [0, 0, 9, 0, 0]

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

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

Решение 1: Два массива для префиксов и суффиксов

function productExceptSelf(nums) {
  const n = nums.length
  const prefix = new Array(n)
  const suffix = new Array(n)
  const result = new Array(n)

  // Вычисляем префиксные произведения
  prefix[0] = 1
  for (let i = 1; i < n; i++) {
    prefix[i] = prefix[i - 1] * nums[i - 1]
  }

  // Вычисляем суффиксные произведения
  suffix[n - 1] = 1
  for (let i = n - 2; i >= 0; i--) {
    suffix[i] = suffix[i + 1] * nums[i + 1]
  }

  // Формируем результат
  for (let i = 0; i < n; i++) {
    result[i] = prefix[i] * suffix[i]
  }

  return result
}

Анализ решения:

✅ Понятная логика работы

✅ Линейная временная сложность O(n)

❌ Дополнительная память O(n)

❌ Три прохода по массиву

Решение 2: Оптимизация по памяти (один массив)

function productExceptSelf(nums) {
  const n = nums.length
  const result = new Array(n)

  // Заполняем префиксными произведениями
  result[0] = 1
  for (let i = 1; i < n; i++) {
    result[i] = result[i - 1] * nums[i - 1]
  }

  // Умножаем на суффиксные произведения
  let suffix = 1
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffix
    suffix *= nums[i]
  }

  return result
}

Характеристики:

✅ Оптимальное использование памяти O(1)

✅ Только два прохода по массиву

✅ Линейная временная сложность O(n)

❌ Менее очевидная логика работы

Решение 3: С обработкой нулей (учет особых случаев)

function productExceptSelf(nums) {
  const n = nums.length
  const result = new Array(n)

  // Подсчитываем количество нулей и общее произведение без нулей
  let zeroCount = 0
  let productWithoutZero = 1

  for (const num of nums) {
    if (num === 0) {
      zeroCount++
    } else {
      productWithoutZero *= num
    }
  }

  // Заполняем результат в зависимости от количества нулей
  for (let i = 0; i < n; i++) {
    if (zeroCount > 1) {
      result[i] = 0
    } else if (zeroCount === 1) {
      result[i] = nums[i] === 0 ? productWithoutZero : 0
    } else {
      result[i] = productWithoutZero / nums[i] // В реальном решении не используем деление
    }
  }

  return result
}

Преимущества и недостатки:

✅ Эффективная обработка особых случаев

✅ Понятная логика работы

❌ Использует деление (не соответствует требованиям)

❌ Требует дополнительных проверок

Рекомендации по решению

1. Выбор метода решения:

   • Использовать префиксные и суффиксные произведения
   • При ограничениях по памяти использовать решение с одним массивом
   • Обратить внимание на обработку случаев с нулями

2. Важные моменты:

   • Правильная инициализация результирующего массива
   • Аккуратная работа с граничными элементами
   • Избегание переполнения

Распространённые ошибки

1. Использование деления несмотря на ограничение
2. Неправильная обработка крайних случаев
3. Неоптимальное использование памяти

Оптимизации

Оптимизация с кешированием

function productExceptSelf(nums) {
  const n = nums.length
  const result = new Array(n).fill(1)

  let leftProduct = 1
  let rightProduct = 1

  for (let i = 0; i < n; i++) {
    result[i] *= leftProduct
    result[n - 1 - i] *= rightProduct
    leftProduct *= nums[i]
    rightProduct *= nums[n - 1 - i]
  }

  return result
}

Заключение

При решении задачи важно учитывать:

• Ограничение на использование деления
• Требование линейной временной сложности
• Возможность оптимизации пространственной сложности
• Корректную обработку особых случаев

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