题目链接:https://leetcode-cn.com/problems/product-of-array-except-self/
题目描述
分析
1. 双重循环
时间复杂度:O(n^2)，不通过
2. 循环
先所有数相乘，循环时再除以自身，不符合要求，不通过
3. 指针
左右指针相乘 -> 解析
代码实现
public enum Q238 {
instance;
// O(n^2)
public int[] productExceptSelf(int[] nums) {
int l=nums.length;
int[] target=new int[l];
for(int i=0;i<l;i++){
int multiply=1;
for(int j=0;j<l;j++){
if(i!=j){
multiply*=nums[j];
}
}
target[i]=multiply;
}
return target;
}
// O(n)
public int[] productExceptSelf1(int[] nums) {
int multiply=1;
for(int num:nums){
multiply*=num;
}
for(int i=0;i<nums.length;i++){
nums[i]=multiply/nums[i];
}
return nums;
}
// O(n)
public int[] productExceptSelf2(int[] nums) {
int left = 1;
int right = 1;
int len = nums.length;
int[] output = new int[len];
for(int i=0;i<len;i++){
output[i] = left;
left *= nums[i];
}
for(int j=len-1;j>=0;j--){
output[j] *= right;
right *= nums[j];
}
return output;
}
public static void main(String[] args) {
// assert [24, 12, 8, 6]
SystemUtil.print(Q238.instance.productExceptSelf(new int[]{1,2,3,4}));
SystemUtil.print(Q238.instance.productExceptSelf1(new int[]{1,2,3,4}));
SystemUtil.print(Q238.instance.productExceptSelf2(new int[]{1,2,3,4}));
}
}
