阵列的产物自self -leetcode java解决方案-DEV365 开发者社区

您好读者，让我们现在解决一个leetcode问题。

在此博客中，让我们解决问题Product of Array Except Self是Blind 75 List of LeetCode Problems。

这是一个带有多个潜在解决方案的LeetCode媒介问题，我们将在此博客中通过。

了解问题

问题的目的是计算输入数组中所有元素的乘积，除每个索引处的元素外。该问题还提到编写一种在O(n)时间和不使用部门操作的情况下运行的算法。

了解测试箱

要测试解决方案，我们可以考虑以下情况：

输入：[1, 2, 3, 4] 输出：[24, 12, 8, 6] 说明：除索引0的所有元素的乘积是2 * 3 * 4 = 24。除索引1处的所有元素的乘积是1 * 3 * 4 = 12.类似地，对于索引2，产品是1 * 2 * 4 = 8，对于索引3，产品为1 * 2 * 3 = 6。
输入：[4, 2, 1, 5, 3] 输出：[30, 60, 120, 24, 40] 说明：除索引0的所有元素的乘积是2 * 1 * 5 * 3 = 30。除索引1处的所有元素的乘积是4 * 1 * 5 * 3 =60。同样，对于索引2，产品为4 * 2 * 5 * 3 = 120，对于索引3，产品为4 * 2 * 1 * 3 = 24，对于索引4，产品为4 * 2 * 1 * 5 = 40。
输入：[1, 1, 1, 1, 1] 输出：[1, 1, 1, 1, 1] 说明：由于所有元素都是相同的，因此除每个索引上的一个元素外，所有元素的产物本身将是相同的元素。
输入：[0, 0, 0, 0]7 输出：[0, 0, 0, 0] 说明：由于输入数组中的值为零，因此除每个索引的一个元素的乘积都为零。
输入：[2, 3, 0, 4] 输出：[0, 0, 24, 0] 说明：除索引0是3 * 0 * 4 = 0以外的所有元素的乘积。除索引1的所有元素的乘积是2 * 0 * 4 = 0。对于索引2，产品为2 * 3 * 4 = 24，对于索引3，产品为2 * 3 * 0 = 0。

蛮力方法

蛮力方法将是计算数组中所有值的乘积，除了使用两个嵌套迭代的当前值。

关键点：

对于每个值，通过两次通过数组迭代来计算所有其他值的乘积。
此方法使用两个嵌套环将每个元素与其他所有元素相乘，不包括本身。
但是，此方法效率低下，可能会导致更大的测试用例超过时间限制（TLE）误差。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] answer = new int[size];
        for(int i=0; i<size; i++) {
            answer[i] = 1;
        }
        for(int i=0; i<size; i++) {
            for(int j=0; j<size; j++) {
                if(i==j) continue;
                answer[i] *= nums[j];
            }
        }
        return answer;
    }
}

时间复杂性：O（n^2）

蛮力方法的时间复杂性是二次的，因为它涉及嵌套通过数组的嵌套环。

空间复杂性：O（1）

蛮力方法不需要除答案阵列以外的其他空间，因此空间复杂性是恒定的。

更好的方法

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int size = nums.length;
        int[] answer = new int[size];
        int[] prefix =  new int[size];
        int[] suffix =  new int[size];
        int temp = 1;
        for(int i=0; i<size; i++) {
            prefix[i] = temp;
            temp *= nums[i];
        }
        temp = 1;
        for(int j=size-1; j>=0; j--) {
            suffix[j] = temp;
            temp *= nums[j];
        }
        for(int i=0; i<size; i++) {
            answer[i] = prefix[i] * suffix[i];
        }
        return answer;
    }
}

关键点：

更好的方法使用单独的迭代来计算每个元素的前缀和后缀值。
在这种方法中，我们在从左到右横穿数组并将其存储在前缀数组中时计算前缀产品。
然后，我们在从右到左右横穿数组并将其存储在后缀数组中时计算后缀产品。
最后，我们将相应的前缀和后缀值乘以获取最终产品。

时间复杂性：o（n）

更好的方法执行两个线性通过阵列，从而导致线性时间复杂性。

空间复杂性：o（n）

更好的方法需要额外的空间来存储前缀和后缀阵列，从而导致线性空间复杂性。

最佳方法

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] answer = new int[nums.length];

        int prefix = 1;
        for(int i=0; i<nums.length; i++) {
            answer[i] = prefix;
            prefix *= nums[i];
        }

        int suffix = 1;
        for(int j=nums.length-1; j>=0; j--) {
            answer[j] *= suffix;
            suffix *= nums[j];
        }

        return answer;
    }
}