238题：除自身以外数组的乘积

238题：除自身以外数组的乘积

写作背景：由于最近在练习leetcode，这道题刚开始思路不太清晰，所以将自己的解题思路记录下来，以便后续复习。

题目描述：

• 给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
• 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
• 请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
• 示例 1:
• 输入: nums = [1,2,3,4]
• 输出: [24,12,8,6]
• 示例 2:
• 输入: nums = [-1,1,0,-3,3]
• 输出: [0,0,9,0,0]
• 提示：

• 2 <= nums.length <= 105
  

• -30 <= nums[i] <= 30
  

• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内
  

• 进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

解题思路：

• 1.暴力解法：遍历数组，每次遍历时，将当前元素置为1，然后遍历数组，将其他元素相乘，得到结果，将结果放入结果数组中，时间复杂度为O(n^2)
• 2.优化解法：遍历一遍数组，得到数组的乘积，然后遍历数组，将数组的乘积除以当前元素，得到结果，将结果放入结果数组中，时间复杂度为O(n)
• 难点：不能使用除法，且时间复杂度为O(n)
• 解决思路：使用乘积倒数来计算结果。

public class P238 {

    public int[] productExceptSelf(int[] nums) {
        if (nums.length == 0){
            return nums;
        }
        int sumMultiply = 1;
        int[] res = new int[nums.length];
        int zeroCount = 0;
        int zeroPos = -1;

        for (int i = 0;i< nums.length;i++) {
            if (0 != nums[i])
                sumMultiply *= nums[i];
            else {
                zeroCount++;
                zeroPos = i;
            }
        }

        if (zeroCount > 1)
            return res;
        else if (zeroCount == 1) {
            res[zeroPos] = sumMultiply;
            return res;
        }else {
            for (int i = 0;i<nums.length;i++) {
                res[i] = (int) (sumMultiply * calculateReciprocal(nums[i]));
            }
        }
        return res;
    }

    // 计算一个数的倒数
    private static double calculateReciprocal(int val) {
        if (val == 0) {
            return 0;
        }

        boolean negative = false;
        // 判断是否是负数
        if (val < 0) {
            negative = true;
            val = -val;
        }
        int iniVal = 1;
        double iniInt = 1.0;
        double iniDouble = 0.1;
        double finalVal = 0.0;
        int maxAcc = 16;
        int iniAcc = 0;

        do {
            int count = 0;
            // 将 iniInt 和 iniVal 调整到适当的范围
            while (iniVal < val) {
                iniVal *= 10;
                iniInt *= iniDouble;
            }

            // 计算倒数的整数部分
            while (iniVal >= val) {
                iniVal -= val;
                count++;
            }

            // 累加整数部分
            finalVal += iniInt * count;
            iniAcc++;
        } while (iniVal != 0 && iniAcc < maxAcc);

        return negative ? -finalVal : finalVal;
    }
}

• 3.还可以通过数学方法计算一个数倒数并且不涉及除法，解决方法：使用对数来计算倒数，即：1/x = e^(-ln(x))，这样就可以使用乘积倒数来计算结果。
  但是此方法由于java中的double类型精度问题，导致结果不准确，所以不推荐使用，但是可以作为一种思路。

public class P238 {

    public int[] productExceptSelf(int[] nums) {
        if (nums.length == 0){
            return nums;
        }
        int sumMultiply = 1;
        int[] res = new int[nums.length];
        int zeroCount = 0;
        int zeroPos = -1;

        for (int i = 0;i< nums.length;i++) {
            if (0 != nums[i])
                sumMultiply *= nums[i];
            else {
                zeroCount++;
                zeroPos = i;
            }
        }

        if (zeroCount > 1)
            return res;
        else if (zeroCount == 1) {
            res[zeroPos] = sumMultiply;
            return res;
        }else {
            for (int i = 0;i<nums.length;i++) {
                res[i] = (int) (sumMultiply * calculateReciprocal(nums[i]));
            }
        }
        return res;
    }

    // 计算一个数的倒数
    private static double calculateReciprocal(int val) {
        if (val == 0) {
            return 0;
        }
        boolean negative = false;
        // 判断是否是负数
        if (val < 0) {
            negative = true;
            val = -val;
        }
        return negative ? -Math.exp(-Math.log(val)) : Math.exp(-Math.log(val));
    }
}