给定一个大小为 n 的整数数组arr【】，任务是找到数组的所有子数组的乘积。 举例:
输入: arr[] = {2，4} 输出: 64 解释: 这里，子阵是{2}、{2，4}和{4}。 每个子阵的产品是 2、8、4。 所有子阵列的乘积= 64 输入: arr[] = {1，2，3} 输出: 432 说明: 这里，子阵列为{1}、{1，2}、{1，2，3}、{2}、{2，3}、{3}。 每个子阵的产品是 1、2、6、2、6、3。 所有子阵列的乘积= 432
天真迭代的方法:这些方法请参考本帖。 方法:想法是统计所有子阵列中出现的每个元素的数量。为了计数，我们有以下观察:
- 在以 arr[i] 开始的每个子阵列中，都有以元素 arr[i] 开始的(n–i)这样的子集。 例如:
对于数组 arr[] = {1，2，3} n = 3，对于元素 2，即索引= 1 有(n–索引)= 3–1 = 2 的子集 {2}和{2，3}
- 对于任何元素 arr[i] ，都有(n–i)* i子阵列，其中 arr[i] 不是第一个元素。
对于数组 arr[] = {1，2，3} n = 3，对于元素 2，即索引= 1 有(n–索引)索引=(3–1) 1 = 2 个子集，其中 2 不是第一个元素。 {1，2}和{1，2，3}
因此，根据以上观察，每个元素的总数arr【i】出现在所有子阵列中，每个索引 i 由下式给出:
total_elements = (n - i) (n - i)*i
total_elements = (n - i)*(i 1)
其思想是将每个元素(n–i)*(i 1)的次数相乘，得到所有子阵列中元素的乘积。 以下是上述办法的实施情况:
c
// c program for the above approach
#include
using namespace std;
// function to find the product of
// elements of all subarray
long int subarrayprodct(int arr[],
int n)
{
// initialize the result
long int result = 1;
// computing the product of
// subarray using formula
for (int i = 0; i < n; i )
result *= pow(arr[i],
(i 1) * (n - i));
// return the product of all
// elements of each subarray
return result;
}
// driver code
int main()
{
// given array arr[]
int arr[] = { 2, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
// function call
cout << subarrayprodct(arr, n)
<< endl;
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java program for the above approach
import java.util.*;
class gfg{
// function to find the product of
// elements of all subarray
static int subarrayprodct(int arr[], int n)
{
// initialize the result
int result = 1;
// computing the product of
// subarray using formula
for(int i = 0; i < n; i )
result *= math.pow(arr[i], (i 1) *
(n - i));
// return the product of all
// elements of each subarray
return result;
}
// driver code
public static void main(string[] args)
{
// given array arr[]
int arr[] = new int[]{2, 4};
int n = arr.length;
// function call
system.out.println(subarrayprodct(arr, n));
}
}
// this code is contributed by pratima pandey
python 3
# python3 program for the above approach
# function to find the product of
# elements of all subarray
def subarrayprodct(arr, n):
# initialize the result
result = 1;
# computing the product of
# subarray using formula
for i in range(0, n):
result *= pow(arr[i],
(i 1) * (n - i));
# return the product of all
# elements of each subarray
return result;
# driver code
# given array arr[]
arr = [ 2, 4 ];
n = len(arr);
# function call
print(subarrayprodct(arr, n))
# this code is contributed by code_mech
c
// c# program for the above approach
using system;
class gfg{
// function to find the product of
// elements of all subarray
static int subarrayprodct(int []arr, int n)
{
// initialize the result
int result = 1;
// computing the product of
// subarray using formula
for(int i = 0; i < n; i )
result *= (int)(math.pow(arr[i], (i 1) *
(n - i)));
// return the product of all
// elements of each subarray
return result;
}
// driver code
public static void main()
{
// given array arr[]
int []arr = new int[]{2, 4};
int n = arr.length;
// function call
console.write(subarrayprodct(arr, n));
}
}
// this code is contributed by code_mech
java 描述语言
output:
64
时间复杂度: o(n) ，其中 n 为元素个数。 t5【辅助空间: o(1)
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
