Ming
0%

LeetCode-238

Posted on Edited on In

题目

结果

代码

直接（暴力）法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            output[i] = multiply(i, nums);
        }
        return output;
    }

    private int multiply(int index, int[] nums) {
        int ans = 1;
        for (int i = 0; i < nums.length; i++) {
            if (i != index) {
                ans *= nums[i];
            }
        }
        return ans;
    }
}

除法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] output = new int[nums.length];
        int mul = Arrays.stream(nums).reduce(1, (acc, n) -> acc * n);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                output[i] = mul / nums[i];
            } else {
                output[i] = multiply(i, nums);
            }
        }
        return output;
    }

    private int multiply(int index, int[] nums) {
        int ans = 1;
        for (int i = 0; i < nums.length; i++) {
            if (i != index) {
                ans *= nums[i];
            }
        }
        return ans;
    }
}

左右乘积法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] left = new int[nums.length];
        int[] right = new int[nums.length];
        int[] output = new int[nums.length];
        
        left[0] = 1;
        left[1] = nums[0];
        right[nums.length - 1] = 1;
        right[nums.length - 2] = nums[nums.length - 1];
        
        for (int i = 2; i < nums.length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
            right[nums.length - i - 1] = right[nums.length - i] * nums[nums.length - i];
        }
        
        for (int i = 0; i < nums.length; i++) {
            output[i] = left[i] * right[i];
        }
        return output;
    }
}

复杂度

直接（暴力法）

  • 时间复杂度：O（n²）

  • 空间复杂度：O（1）输出数组不被视为额外空间

除法

  • 时间复杂度：根据0的个数，最坏情况下是O（n²），一般情况是O（n）

  • 空间复杂度：O（1）输出数组不被视为额外空间

左右乘积法：

  • 时间复杂度：O（n）

  • 空间复杂度：O（n）