不包含本位置值的累乘数组

[编程题]不包含本位置值的累乘数组

热度指数：3346 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组arr，返回不包含本位置值的累乘数组

例如，arr=[2,3,1,4]，返回[12, 8, 24, 6]，即除自己外，其他位置上的累乘

[要求]

时间复杂度为

，额外空间复杂度为

输入描述:

第一行有两个整数N, P。分别表示序列长度，模数(即输出的每个数需要对此取模)
接下来一行N个整数表示数组内的数

输出描述:

输出N个整数表示答案

示例1

输入

4 100000007
2 3 1 4

输出

12 8 24 6

备注:

算法知识视频讲解

Java

想润的我反对画饼

//构建非乘积数组,不用除法,我看到下面有考虑0的,不用出发就不用考虑0

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
int P = in.nextInt();
long[] arr = new long[N];
int firnu = 0;
while (in.hasNextLong()) {
arr[firnu++] = in.nextLong();
}
Long [] rearr = new Long[N];
rearr[0] = 1l;
for (int i = 1; i < N; i++ ) {
rearr[i] = rearr[i - 1] * arr[i - 1] % P;
}
long temp = 1;
for (int i = N - 2 ; i >= 0; i--) {
temp = (temp * arr[i + 1]) % P;
rearr[i] = rearr[i] * temp % P;
}
for (int i = 0; i < N; i++) {
System.out.print(rearr[i] + " ");
}
}
}

发表于 2022-04-12 22:29:12 回复(0)

Java

小星教授

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		int n = scanner.nextInt();
        int p = scanner.nextInt();
        long[] arr = new long[n];
        for(int i=0;i<n;i++){
            arr[i] = scanner.nextInt();
        }
       
        long[] lr = new long[n];
        long[] rl = new long[n];
        
        lr[0]=1;
        rl[n-1]=1;
        for(int i=1;i<n;i++){
            lr[i] = lr[i-1] * arr[i-1] % p;
        }
        for(int i=n-2;i>=0;i--){
            rl[i] = rl[i+1] * arr[i+1] % p;
        }
        
        for(int i=0;i<n;i++){
            System.out.print(lr[i]*rl[i]%p+" ");
        }
        
	}
}

发表于 2019-10-24 19:32:19 回复(0)