Ежедневная проблема кодирования № 2:
Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i. For example, if our input was [1, 2, 3, 4, 5], the expected output would be [120, 60, 40, 30, 24]. If our input was [3, 2, 1], the expected output would be [2, 3, 6].
Решение грубой силы
Решение грубой силы является наиболее интуитивным подходом. Обычно нужно понять, как работает человеческий разум, и превратить это в код.
Как работает наш мозг: мы пройдемся по массиву и для каждого слота/индекса умножим значения, которых нет в слоте i
, и поместим продукт в новый множество. Продолжаем, пока не достигнем конца массива.
const calculateProduct = (array) => { for (let i = 0; i < array.length; i++) { let product = 1; for (let j = 0; j < array.length; j++) { if (j !== i) { const currentValue = array[j]; product = product * currentValue; } } results[i] = product; } return results; };
Мы будем перебирать массив в for loop
. Мы инициализируем переменную product
значением 1.
Затем у нас будет второй for loop
, который также начинается с 0, но будет проверка, чтобы убедиться, что мы умножаем значение только при i !== j
. После прохода по массиву для индекса i
мы устанавливаем продукт в массиве results
. В конце мы возвращаем массив results
.
Решение O(n)
Учитывая, что это проблема кодирования, должен быть гораздо лучший подход, чем решение грубой силы O (n²). И есть!
Что мы можем сделать, так это найти общее произведение всех значений в массиве, пройдя по массиву один раз, что равно O (n). Затем мы повторяем второй раз, который также равен O(n), но на этот раз мы разделим произведение на значение в текущем индексе i
и поместим результат в массив results
. Общая временная сложность составляет O(2n) или просто O(n).
const calculateProduct = (array) => { const results = []; let product = 1; for (let i = 0; i < array.length; i++) { const currentValue = array[i]; product = product * currentValue; } for (let j = 0; j < array.length; j++) { const currentValue = array[j]; const result = product / currentValue; results.push(result); } return results; };
O(n) без деления
Чтобы найти решение без использования деления, мы должны использовать дополнительное пространство для этого компромисса. У нас будет два дополнительных массива для вычисления накопительного произведения слева и справа от индекса.
const calculateProduct = (array) => { const left = []; const right = []; const results = []; for (let i = 0; i < array.length; i++) { left[i] = (left[i - 1] * array[i - 1]) || 1; } for (let j = array.length - 1; j >= 0; j--) { right[j] = (right[j + 1] * array[j + 1] || 1); } for (let k = 0; k < array.length; k++) { results[k] = left[k] * right[k]; } return results; };
Решения в моем REPL: https://repl.it/@etea13/Product-in-an-Array