我们有一个整数数组和一组范围查询。对于每个查询，我们都需要找到给定范围内元素的乘积。 例子：
null
Input : arr[] = {5, 10, 15, 20, 25} queries[] = {(3, 5), (2, 2), (2, 3)}Output : 7500, 10, 1507500 = 15 x 20 x 2510 = 10150 = 10 x 15
A. 缺乏经验的 方法是从下到上浏览数组中的每个元素，并将所有元素相乘以找到乘积。每个查询的时间复杂度为O（n）。 一 有效率的 方法是采用另一个数组，并将所有元素的乘积存储到数组的第i个索引中具有索引i的元素。但这里有一个陷阱。如果数组中的任何元素为0，则从那时起，dp数组将包含0。因此，我们应该得到0作为我们的答案，即使0不在下限和上限之间。 为了解决这个问题，我们使用了另一个名为countZeros的数组，它将包含该数组包含的“0”的个数，直到索引i。 现在如果 countZeros[上限]-countZeros[下限]>0 ，表示该范围内有一个0，因此答案为0。否则我们就照办。
C++
// C++ program for array // range product queries #include<bits/stdc++.h> using namespace std; // Answers product queries // given as two arrays // lower[] and upper[]. void findProduct( long arr[], int lower[], int upper[], int n, int n1) { long preProd[n]; int countZeros[n]; long prod = 1; // stores the product // keeps count of zeros int count = 0; for ( int i = 0; i < n; i++) { // if arr[i] is 0, we increment // count and do not multiply // it with the product if (arr[i] == 0) count++; else prod *= arr[i]; // store the value of prod in dp preProd[i] = prod; // store the value of // count in countZeros countZeros[i] = count; } // We have preprocessed // the array, let us // answer queries now. for ( int i = 0; i < n1; i++) { int l = lower[i]; int u = upper[i]; // range starts from // first element if (l == 1) { // range does not // contain any zero if (countZeros[u - 1] == 0) cout << (preProd[u - 1]) << endl; else cout<<0<<endl; } else // range starts from // any other index { // no difference in countZeros // indicates that there are no // zeros in the range if (countZeros[u - 1] - countZeros[l - 2] == 0) cout << (preProd[u - 1] / preProd[l - 2]) << endl; else // zeros are present in the range cout << 0 << endl; } } } // Driver code int main() { long arr[] ={ 0, 2, 3, 4, 5 }; int lower[] = {1, 2}; int upper[] = {3, 2}; findProduct(arr, lower, upper,5,2); return 0; } // This code is contributed // by Arnab Kundu |
JAVA
// Java program for array range product queries class Product { // Answers product queries given as two arrays // lower[] and upper[]. static void findProduct( long [] arr, int [] lower, int [] upper) { int n = arr.length; long [] preProd = new long [n]; int [] countZeros = new int [n]; long prod = 1 ; // stores the product // keeps count of zeros int count = 0 ; for ( int i = 0 ; i < n; i++) { // if arr[i] is 0, we increment count and // do not multiply it with the product if (arr[i] == 0 ) count++; else prod *= arr[i]; // store the value of prod in dp preProd[i] = prod; // store the value of count in countZeros countZeros[i] = count; } // We have preprocessed the array, let us // answer queries now. for ( int i = 0 ; i < lower.length; i++) { int l = lower[i]; int u = upper[i]; // range starts from first element if (l == 1 ) { // range does not contain any zero if (countZeros[u - 1 ] == 0 ) System.out.println(preProd[u - 1 ]); else System.out.println( 0 ); } else // range starts from any other index { // no difference in countZeros indicates that // there are no zeros in the range if (countZeros[u - 1 ] - countZeros[l - 2 ] == 0 ) System.out.println(preProd[u - 1 ] / preProd[l - 2 ]); else // zeros are present in the range System.out.println( 0 ); } } } public static void main(String[] args) { long [] arr = new long [] { 0 , 2 , 3 , 4 , 5 }; int [] lower = { 1 , 2 }; int [] upper = { 3 , 2 }; findProduct(arr, lower, upper); } } |
Python3
# Python 3 program for array range # product queries # Answers product queries given as # lower[] and upper[]. def findProduct(arr,lower, upper, n, n1): preProd = [ 0 for i in range (n)] countZeros = [ 0 for i in range (n)] prod = 1 # stores the product # keeps count of zeros count = 0 for i in range ( 0 , n, 1 ): # if arr[i] is 0, we increment # count and do not multiply # it with the product if (arr[i] = = 0 ): count + = 1 else : prod * = arr[i] # store the value of prod in dp preProd[i] = prod # store the value of count # in countZeros countZeros[i] = count # We have preprocessed the array, # let us answer queries now. for i in range ( 0 , n1, 1 ): l = lower[i] u = upper[i] # range starts from first element if (l = = 1 ): # range does not contain any zero if (countZeros[u - 1 ] = = 0 ): print ( int (preProd[u - 1 ])) else : print ( 0 ) else : # range starts from any other index # no difference in countZeros indicates # that there are no zeros in the range if (countZeros[u - 1 ] - countZeros[l - 2 ] = = 0 ): print ( int (preProd[u - 1 ] / preProd[l - 2 ])) else : # zeros are present in the range print ( 0 ) # Driver code if __name__ = = '__main__' : arr = [ 0 , 2 , 3 , 4 , 5 ] lower = [ 1 , 2 ] upper = [ 3 , 2 ] findProduct(arr, lower, upper, 5 , 2 ) # This code is contributed by # Sahil_Shelangia |
C#
// C# program for array // range product queries using System; class GFG { // Answers product queries // given as two arrays // lower[] and upper[]. static void findProduct( long [] arr, int [] lower, int [] upper) { int n = arr.Length; long [] preProd = new long [n]; int [] countZeros = new int [n]; long prod = 1; // stores the product // keeps count of zeros int count = 0; for ( int i = 0; i < n; i++) { // if arr[i] is 0, we increment // count and do not multiply it // with the product if (arr[i] == 0) count++; else prod *= arr[i]; // store the value // of prod in dp preProd[i] = prod; // store the value of // count in countZeros countZeros[i] = count; } // We have preprocessed // the array, let us // answer queries now. for ( int i = 0; i < lower.Length; i++) { int l = lower[i]; int u = upper[i]; // range starts from // first element if (l == 1) { // range does not // contain any zero if (countZeros[u - 1] == 0) Console.WriteLine(preProd[u - 1]); else Console.WriteLine(0); } // range starts from // any other index else { // no difference in countZeros // indicates that there are no // zeros in the range if (countZeros[u - 1] - countZeros[l - 2] == 0) Console.WriteLine(preProd[u - 1] / preProd[l - 2]); // zeros are present // in the range else Console.WriteLine(0); } } } // Driver Code public static void Main() { long [] arr = {0, 2, 3, 4, 5}; int [] lower = {1, 2}; int [] upper = {3, 2}; findProduct(arr, lower, upper); } } // This code is contributed // by chandan_jnu. |
PHP
<?php // PHP program for array range product queries // Answers product queries given as two arrays // lower[] and upper[]. function findProduct( $arr , $lower , $upper ) { $n = sizeof( $arr ); $preProd = array ( $n ); $countZeros = array ( $n ); $prod = 1; // stores the product // keeps count of zeros $count = 0; for ( $i = 0; $i < $n ; $i ++) { // if arr[i] is 0, we increment count and // do not multiply it with the product if ( $arr [ $i ] == 0) $count ++; else $prod *= $arr [ $i ]; // store the value of prod in dp $preProd [ $i ] = $prod ; // store the value of count in countZeros $countZeros [ $i ] = $count ; } // We have preprocessed the array, let us // answer queries now. for ( $i = 0; $i < sizeof( $lower ); $i ++) { $l = $lower [ $i ]; $u = $upper [ $i ]; // range starts from first element if ( $l == 1) { // range does not contain any zero if ( $countZeros [ $u - 1] == 0) echo ( $preProd [ $u - 1] ); else echo (0); } else // range starts from any other index { // no difference in countZeros indicates that // there are no zeros in the range if ( $countZeros [ $u - 1] - $countZeros [ $l - 2] == 0) echo ( $preProd [ $u - 1] / $preProd [ $l - 2]); else // zeros are present in the range echo (0); } echo "" ; } } // Driver Code $arr = array (0, 2, 3, 4, 5 ); $lower = array (1, 2); $upper = array (3, 2); findProduct( $arr , $lower , $upper ); // This code is contributed // by Mukul Singh |
Javascript
<script> // JavaScript program for array // range product queries // Answers product queries // given as two arrays // lower[] and upper[]. function findProduct(arr, lower, upper) { let n = arr.length; let preProd = new Array(n); preProd.fill(0); let countZeros = new Array(n); countZeros.fill(0); let prod = 1; // stores the product // keeps count of zeros let count = 0; for (let i = 0; i < n; i++) { // if arr[i] is 0, we increment // count and do not multiply it // with the product if (arr[i] == 0) count++; else prod *= arr[i]; // store the value // of prod in dp preProd[i] = prod; // store the value of // count in countZeros countZeros[i] = count; } // We have preprocessed // the array, let us // answer queries now. for (let i = 0; i < lower.length; i++) { let l = lower[i]; let u = upper[i]; // range starts from // first element if (l == 1) { // range does not // contain any zero if (countZeros[u - 1] == 0) document.write(preProd[u - 1] + "</br>" ); else document.write(0 + "</br>" ); } // range starts from // any other index else { // no difference in countZeros // indicates that there are no // zeros in the range if (countZeros[u - 1] - countZeros[l - 2] == 0) document.write( (preProd[u - 1] / preProd[l - 2]) + "</br>" ); // zeros are present // in the range else document.write(0 + "</br>" ); } } } let arr = [0, 2, 3, 4, 5]; let lower = [1, 2]; let upper = [3, 2]; findProduct(arr, lower, upper); </script> |
输出：
02
时间复杂性： O（n） 在创建dp阵列和 O（1） 每查询
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
