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

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

Это классическая задача, требующая логического мышления и оптимизации. Запрет на деление усложняет задачу, но открывает возможность использования префиксного и суффиксного произведения.

Решение 1: Префиксное и суффиксное произведение — O(n) время, O(n) память

Основная идея: для каждого элемента вычислить произведение всех элементов слева и произведение всех элементов справа, затем перемножить их.

public class ProductOfArrayExceptSelf {
    /**
     * Вычисляет произведение всех элементов кроме текущего
     * Подход: префиксное и суффиксное произведение
     * Время: O(n)
     * Пространство: O(n) для массивов prefix и suffix
     */
    public static int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n];
        
        // Массив для хранения произведений слева
        int[] prefix = new int[n];
        prefix[0] = 1;
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }
        
        // Массив для хранения произведений справа
        int[] suffix = new int[n];
        suffix[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }
        
        // Вычисляем результат
        for (int i = 0; i < n; i++) {
            result[i] = prefix[i] * suffix[i];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] input1 = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(input1)));
        // Вывод: [24, 12, 8, 6]
        
        int[] input2 = {2, 3, 4, 5};
        System.out.println(Arrays.toString(productExceptSelf(input2)));
        // Вывод: [60, 40, 30, 24]
    }
}

Как это работает:

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

Префиксные произведения (слева):
prefix[0] = 1
prefix[1] = 1 * 1 = 1
prefix[2] = 1 * 2 = 2
prefix[3] = 2 * 3 = 6

Суффиксные произведения (справа):
suffix[0] = 2 * 3 * 4 = 24
suffix[1] = 3 * 4 = 12
suffix[2] = 4 = 4
suffix[3] = 1

Результат:
result[0] = prefix[0] * suffix[0] = 1 * 24 = 24
result[1] = prefix[1] * suffix[1] = 1 * 12 = 12
result[2] = prefix[2] * suffix[2] = 2 * 4 = 8
result[3] = prefix[3] * suffix[3] = 6 * 1 = 6

Решение 2: Оптимизированное — O(n) время, O(1) дополнительная память

Мы можем использовать результирующий массив для хранения префиксных произведений, а суффиксные вычислять на лету:

public class ProductOfArrayOptimized {
    /**
     * Оптимизированная версия с O(1) дополнительной памятью
     * Время: O(n)
     * Пространство: O(1) дополнительно (не считая результирующий массив)
     */
    public static int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n];
        
        // Заполняем result префиксными произведениями
        result[0] = 1;
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        // Проходим справа и вычисляем суффиксные произведения
        int suffixProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] = result[i] * suffixProduct;
            suffixProduct *= nums[i];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int[] input = {1, 2, 3, 4};
        System.out.println(Arrays.toString(productExceptSelf(input)));
        // Вывод: [24, 12, 8, 6]
    }
}

Визуализация оптимизированного подхода:

Шаг 1: Заполняем result префиксными произведениями
result = [1, 1, 2, 6]

Шаг 2: Проходим справа с суффиксным произведением
i=3: result[3] = 6 * 1 = 6, suffixProduct = 1 * 4 = 4
i=2: result[2] = 2 * 4 = 8, suffixProduct = 4 * 3 = 12
i=1: result[1] = 1 * 12 = 12, suffixProduct = 12 * 2 = 24
i=0: result[0] = 1 * 24 = 24, suffixProduct = 24 * 1 = 24

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

Решение 3: Обработка нулей

Если в массиве есть нули, нужна специальная обработка:

public class ProductExceptSelfWithZeros {
    /**
     * Версия с корректной обработкой нулей
     */
    public static int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        int n = nums.length;
        int[] result = new int[n];
        
        // Подсчитываем количество нулей
        int zeroCount = 0;
        int zeroIndex = -1;
        int product = 1;
        
        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                zeroCount++;
                zeroIndex = i;
            } else {
                product *= nums[i];
            }
        }
        
        // Если нулей больше одного, все элементы result будут 0
        if (zeroCount > 1) {
            return result;  // все нули
        }
        
        // Если ровно один ноль
        if (zeroCount == 1) {
            result[zeroIndex] = product;
            return result;
        }
        
        // Если нулей нет, используем стандартный подход
        for (int i = 0; i < n; i++) {
            result[i] = product / nums[i];
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        // Без нулей
        System.out.println(Arrays.toString(productExceptSelf(new int[]{1, 2, 3, 4})));
        // [24, 12, 8, 6]
        
        // С одним нулем
        System.out.println(Arrays.toString(productExceptSelf(new int[]{0, 1, 2, 3})));
        // [6, 0, 0, 0]
        
        // С двумя нулями
        System.out.println(Arrays.toString(productExceptSelf(new int[]{0, 0, 2, 3})));
        // [0, 0, 0, 0]
    }
}

Решение 4: Использование деления (альтернатива)

Если бы деление было разрешено (в некоторых вариантах задачи), решение было бы проще:

public class ProductDivisionApproach {
    /**
     * Простой подход с делением (не рекомендуется для этой задачи)
     */
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        
        // Вычисляем полное произведение
        int totalProduct = 1;
        for (int num : nums) {
            totalProduct *= num;
        }
        
        // Делим на каждый элемент
        for (int i = 0; i < n; i++) {
            result[i] = totalProduct / nums[i];
        }
        
        return result;
    }
}

Проблема: не работает с нулями!

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

На собеседовании

1. Начните с объяснения подхода (префикс + суффикс)
2. Реализуйте основную версию
3. Оптимизируйте по памяти
4. Обсудите граничные случаи (нули, пустой массив)
5. Объясните почему деление не рекомендуется