数组自身以外元素的乘积：三种解法与 Java 代码示例

在 Java 编程中，计算数组自身以外元素的乘积是一个常见的问题。本文将介绍三种不同的解法，并提供相应的 Java 代码示例。

解法一：暴力解法

这种方法的思路是遍历数组，对于每个元素，计算除它之外所有元素的乘积。

public class ProductExceptSelf {
    public static int[] productExceptSelfBruteForce(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        for (int i = 0; i < n; i++) {
            int product = 1;
            for (int j = 0; j < n; j++) {
                if (j!= i) {
                    product *= nums[j];
                }
            }
            result[i] = product;
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] products = productExceptSelfBruteForce(nums);
        for (int product : products) {
            System.out.print(product + " ");
        }
    }
}

这种方法的时间复杂度为 O(n^2)，因为对于每个元素都需要遍历整个数组。

解法二：左右乘积法

通过分别计算每个元素左边所有元素的乘积和右边所有元素的乘积，然后将它们相乘得到最终结果。

public class ProductExceptSelfLeftRight {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftProducts = new int[n];
        int[] rightProducts = new int[n];
        int[] result = new int[n];

        leftProducts[0] = 1;
        for (int i = 1; i < n; i++) {
            leftProducts[i] = leftProducts[i - 1] * nums[i - 1];
        }

        rightProducts[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProducts[i] = rightProducts[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++) {
            result[i] = leftProducts[i] * rightProducts[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] products = productExceptSelf(nums);
        for (int product : products) {
            System.out.print(product + " ");
        }
    }
}

这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)。

解法三：优化的左右乘积法

在前一种方法的基础上，通过只使用一个结果数组来优化空间复杂度。

public class ProductExceptSelfOptimized {
    public static int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

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

        int rightProduct = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4};
        int[] products = productExceptSelf(nums);
        for (int product : products) {
            System.out.print(product + " ");
        }
    }
}

这种优化后的方法时间复杂度仍为 O(n)，但空间复杂度降低为 O(1)，不使用额外的数组来存储左右乘积。

以上就是计算数组自身以外元素乘积的三种解法及相应的 Java 代码示例，您可以根据实际需求选择合适的方法。