使用 oh-my-zsh

题目

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

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

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。

说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。

提示：

• $2 <= nums.length <= 10^5$
• -30 <= nums[i] <= 30

进阶：

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

链接：https://leetcode-cn.com/problems/product-of-array-except-self

题解

1、用减法模拟除法

注意：数组中有0的情况和有负数的情况！！！

• 初始化除0之外的累积变量 product
• 初始化结果数组
• 统计0的个数
• 初始化非0值的位置标记
• 遍历数组
  • 对非0值，累积
    • 标记为1
  • 对0值统计个数
    • 标记为0
• 遍历数组
  • 对于0值
    • 0值数量大于1，也为0
    • 否则 除0值之外的累积为product
  • 对于非0值
    • 0值数量等于0
      • 模拟除法，求除了自己之外的累积值
        • 负数处理，标记结果的正负
        • 实施二进制除法模拟
        • 处理结果正负
        • 返回
    • 0值数量>0
      • 累积值为0

返回结果

class Solution {
    
    public int[] productExceptSelf(int[] nums) {
        int product = 1;
        int[] res = new int[nums.length];
        int count = 0;
        int[] isZero = new int[nums.length];
        // 暴力
        for (int i = 0;i < nums.length;i++) {
            // 不乘0
            if (nums[i] != 0) {
                product *= nums[i];
                isZero[i] = 1;
            } else {
                count++;
                isZero[i] = 0;
            }
        }
        // System.out.println("product: " + product);

        for (int i = 0;i < nums.length;i++) {
            if (isZero[i] == 0) {
                if (count > 1){
                    res[i] = 0;
                } else {
                    res[i] = product;
                }
            } else {
                if (count == 0) {
                    // 模拟除法运算，避免直接用除法
                    res[i] = divide(product, nums[i]);
                } else {
                    res[i] = 0;
                }
            }
        }
        return res;
    }

    // 用减法模拟除法
    private int divide(int product, int num) {
        
        // System.out.print("product: " + product +", num: " + num);
        boolean isPositive = true;
        if (product < 0) {
            product = -product;
            isPositive = false;
        }
        if (num < 0) {
            num = -num;
            if (!isPositive) {
                isPositive = true;
            } else {
                isPositive = false;
            }
        }
        int ans = 0;
        // 二进制除模拟
        for (int i = 31;i >= 0;i--) {
            // product右移 i 大于 num
            if ((product >> i) >= num) {
                ans += 1 << i;// 加上左移i位置
                product -= (num << i);// 更新product
            }
        }
        if (!isPositive) {
            ans = -ans;
        }
        // System.out.println(", ans: " + ans);
        return ans;
    }
}

2、左右乘积表——左右前缀积

• 初始化左右前缀积数组
• 计算左前缀积，下标i不乘，只乘以前 i - 1个数字
• 计算右前缀积，下标i不乘，只乘以前 length - i + 1个数字
• 计算每个位置的除自己之外的积

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

        int[] L = new int[length];
        int[] R = new int[length];

        int[] answer = new int[length];

        L[0] = 1;
        // 不乘最后一个
        for (int i = 1;i < length;i++) {
            L[i] = nums[i - 1] * L[i - 1];
        }

        R[length - 1] = 1;
        // 不乘第一个
        for (int i = length - 2;i >= 0;i--) {
            R[i] = nums[i + 1] * R[i + 1];
        }

        // 计算结果
        for(int i = 0;i < length;i++) {
            answer[i] = L[i] * R[i];
        }
        return answer;
    }
}

3、优化求L 和 R, 用answer数组代替L或者R

• 先计算左前缀积
• 后用单独变量计算右前缀积，顺便更新左前缀积的结果为最终累积，步骤：
  • 先更新左前缀积的结果为最终累积
  • 后更新右前缀积

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

        int[] answer = new int[length];

        answer[0] = 1;
        // 计算前缀积
        for (int i = 1; i < length;i++) {
            answer[i] = nums[i - 1] * answer[i - 1];
        }

        // 用迭代的R做 后缀前缀积
        int R = 1;

        for (int i = length - 1;i >= 0;i--) {
            answer[i] = answer[i] * R;// 先更新answer
            R *= nums[i];// 在更新R
        }

        return answer;
    }

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com