Перейти к содержанию

Название задания

Ссылка с заданием на литкоде

Описание

Необходимо вернуть массив answer равный по длине полученому массиву чисел nums. В возвращаемом массиве число answer[i] должено быть равно произведению всех чисел nums кроме самого числа nums[i].

Гарантируется, что произведение всех чисел nums непрывышает 32-битные целые числа. Если вы пишете на Python то для вас это мало что изменит, т.к. в Python используется "длинная арифметика"

Алгоритм для ршения задачи должен работать за O(n) без использования оператора деление.

Пример 1:

Входные данные: nums = [1, 2, 3, 4]
Выходные данные: [24, 12, 8, 6]
Объяснение: [2 * 3 * 4, 1 * 3 * 4, 1 * 2 * 4, 1 * 2 * 3]

Пример 2:

Входные данные: nums = [-1, 1, 0, -3, 3]
Выходные данные: [0, 0, 9, 0, 0]

Пример 3:

Входные данные: [20, 10, 20]
Выходные данные: [200, 400, 200]

Идея решения

Всё что нам надо сделать, это перемножить все числа между собой и для каждого числа в массиве получить результат деления этого произведения и текущего числа. Однако, по условию задания мы не можем использовать деление.

Для решения этого задания необходимо знать алгоритм префиксной и постфиксной суммы(произведения). Идея в том, что бы получить "накапливаемую" сумму(в нашем случае произведение) всех чисел до текущего числа - это будет префикс и после текущего числа - это будет суфикс.

Алгоритм решения

Если внимательно изучить первый пример, то можно понять какое будет решение. Рассмотрим пример. [1, 2, 3, 4] - мы имеем изначально [24, 12, 8, 6] - мы должны вернуть [24, 1 * 12, 2 * 4, 6] - можно представить ответ, как перемножение префикса и суфикса для каждой позиции

Такми образом нам необходимо два массива, представляющие префиксы и суфиксы: [1, 1, 2, 6] - число 1 по индексу 0, указано просто как число которое при перемножении не меняет число [24, 12, 4, 1] - каждое число представляет произведение всех чисел расположенных правее него в nums

Поскольку длины массивов, nums, префиксного, суфиксного и результатирующего равны мы можем сразу хранить префиксы в результатирующем массиве. А, зная, что префикс и суффикс это постоянно возрастающее число, то хранить его можно в переменной, а не массиве.

Таким образом наш алгоритм выглядит так: 1. определяем переменные для хранения длины массива, произведения суффикса и массив, равный длине nums 2. заполняем массив result префиксными произведениями. По индексу 0 устанавливаем число 1, далее result[i] равен произведению прошлого числа(result[i-1]) и nums[i-1] 3. итерируем массив nums в обратном порядке, с конца. Для каждого числа, кроме последнего вычисляем суфиксное произведение и умножаем result[i] на него 4. возвращаем результат

Сложность

  • По времени: \(O(N)\) n = len(nums)

Алгоритм два раза проходит по массиву чисел nums, а доступ к элементам массива по индексам осуществляется за константное время. Таким образом алгоритм требует линейного времени для решения - \(O(N)\).

  • По памяти: \(O(N)\) n = len(nums) или \(O(1)\) без учёта выходных данных

Для результатирующего массива выделяется память равная получаемому массиву. Если использовать оценку, где пространственная сложность оценивается без учёта памяти, выделеной для выходных данных, то сложность будет константной. Поскольку кроме выходного массивы мы выделяем лишь две переменные, которым необходимо константное место, то сложность можно оценить как \(O(1)\).

Код решения:

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [1] * n
        suffix_product = 1

        for i in range(1, n):
            result[i] *= nums[i - 1] * result[i - 1]

        for i in range(n-1, -1, -1):
            result[i] *= suffix_product
            suffix_product *= nums[i]

        return result

impl Solution {
    pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
        let n = nums.len();
        let mut result: Vec<i32> = vec![1; n];
        let mut suffix_product: i32 = 1;

        for i in 1..n {
            result[i] *= nums[i - 1] * result[i - 1];
        }

        for i in (0..n).rev() {
            result[i] *= suffix_product;
            suffix_product *= nums[i];
        }

        result
    }
}