题目
给你一个长度为 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值
- 0值数量大于1，也为0
- 否则 除0值之外的累积为product
- 对于非0值
- 0值数量等于0
- 模拟除法，求除了自己之外的累积值
- 负数处理，标记结果的正负
- 实施二进制除法模拟
- 处理结果正负
- 返回
- 模拟除法，求除了自己之外的累积值
- 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
