给定一个由n个整数组成的数组arr[]，构造一个乘积数组prod[]（大小相同），使prod[i]等于除arr[i]之外的所有arr[]元素的乘积。解决它 O（n）时间内无除法运算符 .
null
例子：
Input: arr[] = {10, 3, 5, 6, 2}Output: prod[] = {180, 600, 360, 300, 900}3 * 5 * 6 * 2 product of other array elements except 10 is 18010 * 5 * 6 * 2 product of other array elements except 3 is 60010 * 3 * 6 * 2 product of other array elements except 5 is 36010 * 3 * 5 * 2 product of other array elements except 6 is 30010 * 3 * 6 * 5 product of other array elements except 2 is 900Input: arr[] = {1, 2, 3, 4, 5}Output: prod[] = {120, 60, 40, 30, 24 }2 * 3 * 4 * 5 product of other array elements except 1 is 1201 * 3 * 4 * 5 product of other array elements except 2 is 601 * 2 * 4 * 5 product of other array elements except 3 is 401 * 2 * 3 * 5 product of other array elements except 4 is 301 * 2 * 3 * 4 product of other array elements except 5 is 24
天真的解决方案： 方法： 创建两个额外的空间，即两个额外的数组来存储从开始到该索引的所有数组元素的乘积，另一个数组来存储从数组末尾到该索引的所有数组元素的乘积。 要得到不包括该索引的乘积，将前缀乘积乘以索引i-1，后缀乘积乘以索引i+1。
算法：
- 创建两个数组 前缀 和 后缀 长度 N ，即原始数组的长度，初始化 前缀[0]=1 和 后缀[n-1]=1 还有另一个存储产品的阵列。
- 从第二个索引遍历数组。
- 对于每个索引 我 使现代化 前缀[i] 像 前缀[i]=前缀[i-1]*数组[i-1] ，即将产品储存至 i-1 从数组的开头开始索引。
- 从倒数第二个索引开始遍历数组。
- 对于每个索引 我 使现代化 后缀[i] 像 后缀[i]=后缀[i+1]*数组[i+1] ，即将产品储存至 i+1 从数组末尾开始索引
- 从头到尾遍历阵列。
- 对于每个索引 我 输出将是 前缀[i]*后缀[i] ，数组元素（该元素除外）的乘积。
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1) { cout << 0; return ; } /* Allocate memory for temporary arrays left[] and right[] */ int * left = new int [ sizeof ( int ) * n]; int * right = new int [ sizeof ( int ) * n]; /* Allocate memory for the product array */ int * prod = new int [ sizeof ( int ) * n]; int i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) cout << prod[i] << " " ; return ; } /* Driver code*/ int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The product array is: " ; productArray(arr, n); } // This is code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1) { printf ( "0" ); return ; } /* Allocate memory for temporary arrays left[] and right[] */ int * left = ( int *) malloc ( sizeof ( int ) * n); int * right = ( int *) malloc ( sizeof ( int ) * n); /* Allocate memory for the product array */ int * prod = ( int *) malloc ( sizeof ( int ) * n); int i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) printf ( "%d " , prod[i]); return ; } /* Driver program to test above functions */ int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "The product array is: " ); productArray(arr, n); getchar (); } |
JAVA
class ProductArray { /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1 ) { System.out.print( 0 ); return ; } // Initialize memory to all arrays int left[] = new int [n]; int right[] = new int [n]; int prod[] = new int [n]; int i, j; /* Left most element of left array is always 1 */ left[ 0 ] = 1 ; /* Right most element of right array is always 1 */ right[n - 1 ] = 1 ; /* Construct the left array */ for (i = 1 ; i < n; i++) left[i] = arr[i - 1 ] * left[i - 1 ]; /* Construct the right array */ for (j = n - 2 ; j >= 0 ; j--) right[j] = arr[j + 1 ] * right[j + 1 ]; /* Construct the product array using left[] and right[] */ for (i = 0 ; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0 ; i < n; i++) System.out.print(prod[i] + " " ); return ; } /* Driver program to test the above function */ public static void main(String[] args) { ProductArray pa = new ProductArray(); int arr[] = { 10 , 3 , 5 , 6 , 2 }; int n = arr.length; System.out.println( "The product array is : " ); pa.productArray(arr, n); } } // This code has been contributed by Mayank Jaiswal |
蟒蛇3
# Python implementation of the above approach # Function to print product array for a given array # arr[] of size n def productArray(arr, n): # Base case if (n = = 1 ): print ( 0 ) return # Allocate memory for temporary arrays left[] and right[] left = [ 0 ] * n right = [ 0 ] * n # Allocate memory for the product array prod = [ 0 ] * n # Left most element of left array is always 1 left[ 0 ] = 1 # Right most element of right array is always 1 right[n - 1 ] = 1 # Construct the left array for i in range ( 1 , n): left[i] = arr[i - 1 ] * left[i - 1 ] # Construct the right array for j in range (n - 2 , - 1 , - 1 ): right[j] = arr[j + 1 ] * right[j + 1 ] # Construct the product array using # left[] and right[] for i in range (n): prod[i] = left[i] * right[i] # print the constructed prod array for i in range (n): print (prod[i], end = ' ' ) # Driver code arr = [ 10 , 3 , 5 , 6 , 2 ] n = len (arr) print ( "The product array is:" ) productArray(arr, n) # This code is contributed by ankush_953 |
C#
using System; class GFG { /* Function to print product array for a given array arr[] of size n */ static void productArray( int [] arr, int n) { // Base case if (n == 1) { Console.Write(0); return ; } // Initialize memory to all arrays int [] left = new int [n]; int [] right = new int [n]; int [] prod = new int [n]; int i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) Console.Write(prod[i] + " " ); return ; } /* Driver program to test the above function */ public static void Main() { int [] arr = { 10, 3, 5, 6, 2 }; int n = arr.Length; Console.Write( "The product array is :" ); productArray(arr, n); } } // This code is contributed by nitin mittal. |
PHP
<?php // Function to print product // array for a given array // arr[] of size n function productArray( $arr , $n ) { // Base case if ( $n == 1) { echo "0" ; return ; } // Initialize memory // to all arrays $left = array (); $right = array (); $prod = array (); $i ; $j ; // Left most element of // left array is always 1 $left [0] = 1; // Right most element of // right array is always 1 $right [ $n - 1] = 1; // Construct the left array for ( $i = 1; $i < $n ; $i ++) $left [ $i ] = $arr [ $i - 1] * $left [ $i - 1]; // Construct the right array for ( $j = $n - 2; $j >= 0; $j --) $right [ $j ] = $arr [ $j + 1] * $right [ $j + 1]; // Construct the product array // using left[] and right[] for ( $i = 0; $i < $n ; $i ++) $prod [ $i ] = $left [ $i ] * $right [ $i ]; // print the constructed prod array for ( $i = 0; $i < $n ; $i ++) echo $prod [ $i ], " " ; return ; } // Driver Code $arr = array (10, 3, 5, 6, 2); $n = count ( $arr ); echo "The product array is : " ; productArray( $arr , $n ); // This code has been contributed by anuj_67. ?> |
Javascript
<script> /* Function to print product array for a given array arr[] of size n */ function productArray(arr, n) { // Base case if (n == 1) { document.write(0); return ; } // Initialize memory to all arrays let left = new Array(n); let right = new Array(n); let prod = new Array(n); let i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) document.write(prod[i] + " " ); return ; } // Driver code let arr = [ 10, 3, 5, 6, 2 ]; let n = arr.length; document.write( "The product array is :" + "</br>" ); productArray(arr, n); // This code is contributed by mukesh07. </script> |
输出
The product array is: 180 600 360 300 900
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1) { cout << 0; return ; } /* Allocate memory for temporary arrays left[] and right[] */ int * left = new int [ sizeof ( int ) * n]; int * right = new int [ sizeof ( int ) * n]; /* Allocate memory for the product array */ int * prod = new int [ sizeof ( int ) * n]; int i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) cout << prod[i] << " " ; return ; } /* Driver code*/ int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The product array is: " ; productArray(arr, n); } // This is code is contributed by rathbhupendra |
C
#include <stdio.h> #include <stdlib.h> /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1) { printf ( "0" ); return ; } /* Allocate memory for temporary arrays left[] and right[] */ int * left = ( int *) malloc ( sizeof ( int ) * n); int * right = ( int *) malloc ( sizeof ( int ) * n); /* Allocate memory for the product array */ int * prod = ( int *) malloc ( sizeof ( int ) * n); int i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) printf ( "%d " , prod[i]); return ; } /* Driver program to test above functions */ int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); printf ( "The product array is: " ); productArray(arr, n); getchar (); } |
JAVA
class ProductArray { /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1 ) { System.out.print( 0 ); return ; } // Initialize memory to all arrays int left[] = new int [n]; int right[] = new int [n]; int prod[] = new int [n]; int i, j; /* Left most element of left array is always 1 */ left[ 0 ] = 1 ; /* Right most element of right array is always 1 */ right[n - 1 ] = 1 ; /* Construct the left array */ for (i = 1 ; i < n; i++) left[i] = arr[i - 1 ] * left[i - 1 ]; /* Construct the right array */ for (j = n - 2 ; j >= 0 ; j--) right[j] = arr[j + 1 ] * right[j + 1 ]; /* Construct the product array using left[] and right[] */ for (i = 0 ; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0 ; i < n; i++) System.out.print(prod[i] + " " ); return ; } /* Driver program to test the above function */ public static void main(String[] args) { ProductArray pa = new ProductArray(); int arr[] = { 10 , 3 , 5 , 6 , 2 }; int n = arr.length; System.out.println( "The product array is : " ); pa.productArray(arr, n); } } // This code has been contributed by Mayank Jaiswal |
蟒蛇3
# Python implementation of the above approach # Function to print product array for a given array # arr[] of size n def productArray(arr, n): # Base case if (n = = 1 ): print ( 0 ) return # Allocate memory for temporary arrays left[] and right[] left = [ 0 ] * n right = [ 0 ] * n # Allocate memory for the product array prod = [ 0 ] * n # Left most element of left array is always 1 left[ 0 ] = 1 # Right most element of right array is always 1 right[n - 1 ] = 1 # Construct the left array for i in range ( 1 , n): left[i] = arr[i - 1 ] * left[i - 1 ] # Construct the right array for j in range (n - 2 , - 1 , - 1 ): right[j] = arr[j + 1 ] * right[j + 1 ] # Construct the product array using # left[] and right[] for i in range (n): prod[i] = left[i] * right[i] # print the constructed prod array for i in range (n): print (prod[i], end = ' ' ) # Driver code arr = [ 10 , 3 , 5 , 6 , 2 ] n = len (arr) print ( "The product array is:" ) productArray(arr, n) # This code is contributed by ankush_953 |
C#
using System; class GFG { /* Function to print product array for a given array arr[] of size n */ static void productArray( int [] arr, int n) { // Base case if (n == 1) { Console.Write(0); return ; } // Initialize memory to all arrays int [] left = new int [n]; int [] right = new int [n]; int [] prod = new int [n]; int i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) Console.Write(prod[i] + " " ); return ; } /* Driver program to test the above function */ public static void Main() { int [] arr = { 10, 3, 5, 6, 2 }; int n = arr.Length; Console.Write( "The product array is :" ); productArray(arr, n); } } // This code is contributed by nitin mittal. |
PHP
<?php // Function to print product // array for a given array // arr[] of size n function productArray( $arr , $n ) { // Base case if ( $n == 1) { echo "0" ; return ; } // Initialize memory // to all arrays $left = array (); $right = array (); $prod = array (); $i ; $j ; // Left most element of // left array is always 1 $left [0] = 1; // Right most element of // right array is always 1 $right [ $n - 1] = 1; // Construct the left array for ( $i = 1; $i < $n ; $i ++) $left [ $i ] = $arr [ $i - 1] * $left [ $i - 1]; // Construct the right array for ( $j = $n - 2; $j >= 0; $j --) $right [ $j ] = $arr [ $j + 1] * $right [ $j + 1]; // Construct the product array // using left[] and right[] for ( $i = 0; $i < $n ; $i ++) $prod [ $i ] = $left [ $i ] * $right [ $i ]; // print the constructed prod array for ( $i = 0; $i < $n ; $i ++) echo $prod [ $i ], " " ; return ; } // Driver Code $arr = array (10, 3, 5, 6, 2); $n = count ( $arr ); echo "The product array is : " ; productArray( $arr , $n ); // This code has been contributed by anuj_67. ?> |
Javascript
<script> /* Function to print product array for a given array arr[] of size n */ function productArray(arr, n) { // Base case if (n == 1) { document.write(0); return ; } // Initialize memory to all arrays let left = new Array(n); let right = new Array(n); let prod = new Array(n); let i, j; /* Left most element of left array is always 1 */ left[0] = 1; /* Right most element of right array is always 1 */ right[n - 1] = 1; /* Construct the left array */ for (i = 1; i < n; i++) left[i] = arr[i - 1] * left[i - 1]; /* Construct the right array */ for (j = n - 2; j >= 0; j--) right[j] = arr[j + 1] * right[j + 1]; /* Construct the product array using left[] and right[] */ for (i = 0; i < n; i++) prod[i] = left[i] * right[i]; /* print the constructed prod array */ for (i = 0; i < n; i++) document.write(prod[i] + " " ); return ; } // Driver code let arr = [ 10, 3, 5, 6, 2 ]; let n = arr.length; document.write( "The product array is :" + "</br>" ); productArray(arr, n); // This code is contributed by mukesh07. </script> |
复杂性分析：
- 时间复杂性： O（n）。 数组需要遍历三次，因此时间复杂度为O（n）。
- 空间复杂性： O（n）。 需要两个额外的数组和一个数组来存储输出，因此空间复杂度为O（n）
注： 上述方法可以在空间复杂度O（1）下进行优化。感谢Dileep提出以下解决方案。
高效的解决方案： 方法： 在前面的解决方案中，创建了两个额外的数组来存储前缀和后缀，在这个解决方案中，将前缀和后缀产品存储在输出数组（或产品数组）本身中。从而减少了所需的空间。
算法：
- 创建一个数组 产品 并将其值初始化为1和一个变量 临时雇员 = 1.
- 从头到尾遍历阵列。
- 对于每个索引 我 使现代化 产品[i] 像 产品[i]=温度 和 temp=temp*数组[i] ，即将产品储存至 i-1 从数组的开头开始索引。
- 初始化temp=1，并从最后一个索引开始遍历数组。
- 对于每个索引 我 使现代化 产品[i] 像 产品[i]=产品[i]*温度 和 temp=temp*数组[i] ，即与乘积相乘，直到 i+1 从数组末尾开始索引。
- 打印产品阵列。
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; /* Function to print product array for a given array arr[] of size n */ void productArray( int arr[], int n) { // Base case if (n == 1) { cout << 0; return ; } int i, temp = 1; /* Allocate memory for the product array */ int * prod = new int [( sizeof ( int ) * n)]; /* Initialize the product array as 1 */ memset (prod, 1, n); /* In this loop, temp variable contains product of elements on left side excluding arr[i] */ for (i = 0; i < n; i++) { prod[i] = temp; temp *= arr[i]; } /* Initialize temp to 1 for product on right side */ temp = 1; /* In this loop, temp variable contains product of elements on right side excluding arr[i] */ for (i = n - 1; i >= 0; i--) { prod[i] *= temp; temp *= arr[i]; } /* print the constructed prod array */ for (i = 0; i < n; i++) cout << prod[i] << " " ; return ; } // Driver Code int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); cout << "The product array is: " ; productArray(arr, n); } // This code is contributed by rathbhupendra |
JAVA
class ProductArray { void productArray( int arr[], int n) { // Base case if (n == 1 ) { System.out.print( "0" ); return ; } int i, temp = 1 ; /* Allocate memory for the product array */ int prod[] = new int [n]; /* Initialize the product array as 1 */ for ( int j = 0 ; j < n; j++) prod[j] = 1 ; /* In this loop, temp variable contains product of elements on left side excluding arr[i] */ for (i = 0 ; i < n; i++) { prod[i] = temp; temp *= arr[i]; } /* Initialize temp to 1 for product on right side */ temp = 1 ; /* In this loop, temp variable contains product of elements on right side excluding arr[i] */ for (i = n - 1 ; i >= 0 ; i--) { prod[i] *= temp; temp *= arr[i]; } /* print the constructed prod array */ for (i = 0 ; i < n; i++) System.out.print(prod[i] + " " ); return ; } /* Driver program to test above functions */ public static void main(String[] args) { ProductArray pa = new ProductArray(); int arr[] = { 10 , 3 , 5 , 6 , 2 }; int n = arr.length; System.out.println( "The product array is : " ); pa.productArray(arr, n); } } // This code has been contributed by Mayank Jaiswal |
蟒蛇3
# Python3 program for A Product Array Puzzle def productArray(arr, n): # Base case if n = = 1 : print ( 0 ) return i, temp = 1 , 1 # Allocate memory for the product array prod = [ 1 for i in range (n)] # Initialize the product array as 1 # In this loop, temp variable contains product of # elements on left side excluding arr[i] for i in range (n): prod[i] = temp temp * = arr[i] # Initialize temp to 1 for product on right side temp = 1 # In this loop, temp variable contains product of # elements on right side excluding arr[i] for i in range (n - 1 , - 1 , - 1 ): prod[i] * = temp temp * = arr[i] # Print the constructed prod array for i in range (n): print (prod[i], end = " " ) return # Driver Code arr = [ 10 , 3 , 5 , 6 , 2 ] n = len (arr) print ( "The product array is: n" ) productArray(arr, n) # This code is contributed by mohit kumar |
C#
using System; class GFG { static void productArray( int [] arr, int n) { // Base case if (n == 1) { Console.Write(0); return ; } int i, temp = 1; /* Allocate memory for the product array */ int [] prod = new int [n]; /* Initialize the product array as 1 */ for ( int j = 0; j < n; j++) prod[j] = 1; /* In this loop, temp variable contains product of elements on left side excluding arr[i] */ for (i = 0; i < n; i++) { prod[i] = temp; temp *= arr[i]; } /* Initialize temp to 1 for product on right side */ temp = 1; /* In this loop, temp variable contains product of elements on right side excluding arr[i] */ for (i = n - 1; i >= 0; i--) { prod[i] *= temp; temp *= arr[i]; } /* print the constructed prod array */ for (i = 0; i < n; i++) Console.Write(prod[i] + " " ); return ; } /* Driver program to test above functions */ public static void Main() { int [] arr = { 10, 3, 5, 6, 2 }; int n = arr.Length; Console.WriteLine( "The product array is : " ); productArray(arr, n); } } // This code is contributed by nitin mittal. |
PHP
<?php // PHP program for // A Product Array Puzzle function productArray( $arr , $n ) { // Base case if ( $n == 1) { echo "0" ; return ; } $i ; $temp = 1; /* Allocate memory for the productarray */ $prod = array (); /* Initialize the product array as 1 */ for ( $j = 0; $j < $n ; $j ++) $prod [ $j ] = 1; /* In this loop, temp variable contains product of elements on left side excluding arr[i] */ for ( $i = 0; $i < $n ; $i ++) { $prod [ $i ] = $temp ; $temp *= $arr [ $i ]; } /* Initialize temp to 1 for product on right side */ $temp = 1; /* In this loop, temp variable contains product of elements on right side excluding arr[i] */ for ( $i = $n - 1; $i >= 0; $i --) { $prod [ $i ] *= $temp ; $temp *= $arr [ $i ]; } /* print the constructed prod array */ for ( $i = 0; $i < $n ; $i ++) echo $prod [ $i ], " " ; return ; } // Driver Code $arr = array (10, 3, 5, 6, 2); $n = count ( $arr ); echo "The product array is : " ; productArray( $arr , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> function productArray(arr , n) { // Base case if (n == 1) { document.write( "0" ); return ; } var i, temp = 1; /* Allocate memory for the product array */ var prod = Array(n).fill(0); /* Initialize the product array as 1 */ for (j = 0; j < n; j++) prod[j] = 1; /* In this loop, temp variable contains product of elements on left side excluding arr[i] */ for (i = 0; i < n; i++) { prod[i] = temp; temp *= arr[i]; } /* Initialize temp to 1 for product on right side */ temp = 1; /* In this loop, temp variable contains product of elements on right side excluding arr[i] */ for (i = n - 1; i >= 0; i--) { prod[i] *= temp; temp *= arr[i]; } /* print the constructed prod array */ for (i = 0; i < n; i++) document.write(prod[i] + " " ); return ; } /* Driver program to test above functions */ var arr = [ 10, 3, 5, 6, 2 ]; var n = arr.length; document.write( "The product array is : " ); productArray(arr, n); // This code contributed by Rajput-Ji </script> |
输出
The product array is: 180 600 360 300 900
复杂性分析：
- 时间复杂性： O（n）。 原始数组只需要遍历一次，因此时间复杂度是恒定的。
- 空间复杂性： O（n）。 即使移除了额外的阵列，空间复杂度仍然是O（n），因为产品阵列仍然是必需的。
另一种方法：
将所有元素的乘积存储为一个变量，然后迭代数组，并在新数组中添加product/current_index_值。然后返回这个新数组。
以下是上述方法的实施情况：
C++
// C++ program for the above approach #include <iostream> using namespace std; long * productExceptSelf( int a[], int n) { long prod = 1; long flag = 0; // product of all elements for ( int i = 0; i < n; i++) { // counting number of elements // which have value // 0 if (a[i] == 0) flag++; else prod *= a[i]; } // creating a new array of size n long * arr = new long [n]; for ( int i = 0; i < n; i++) { // if number of elements in // array with value 0 // is more than 1 than each // value in new array // will be equal to 0 if (flag > 1) { arr[i] = 0; } // if no element having value // 0 than we will // insert product/a[i] in new array else if (flag == 0) arr[i] = (prod / a[i]); // if 1 element of array having // value 0 than all // the elements except that index // value , will be // equal to 0 else if (flag == 1 && a[i] != 0) { arr[i] = 0; } // if(flag == 1 && a[i] == 0) else arr[i] = prod; } return arr; } // Driver Code int main() { int n = 5; int array[] = { 10, 3, 5, 6, 2 }; long * ans; ans = productExceptSelf(array, n); for ( int i = 0; i < n; i++) { cout << ans[i] << " " ; } // cout<<"GFG!"; return 0; } // This code is contributed by RohitOberoi. |
JAVA
// Java program for the above approach import java.io.*; import java.util.*; class Solution { public static long [] productExceptSelf( int a[], int n) { long prod = 1 ; long flag = 0 ; // product of all elements for ( int i = 0 ; i < n; i++) { // counting number of elements // which have value // 0 if (a[i] == 0 ) flag++; else prod *= a[i]; } // creating a new array of size n long arr[] = new long [n]; for ( int i = 0 ; i < n; i++) { // if number of elements in // array with value 0 // is more than 1 than each // value in new array // will be equal to 0 if (flag > 1 ) { arr[i] = 0 ; } // if no element having value // 0 than we will // insert product/a[i] in new array else if (flag == 0 ) arr[i] = (prod / a[i]); // if 1 element of array having // value 0 than all // the elements except that index // value , will be // equal to 0 else if (flag == 1 && a[i] != 0 ) { arr[i] = 0 ; } // if(flag == 1 && a[i] == 0) else arr[i] = prod; } return arr; } // Driver Code public static void main(String args[]) throws IOException { int n = 5 ; int [] array = { 10 , 3 , 5 , 6 , 2 }; Solution ob = new Solution(); long [] ans = new long [n]; ans = ob.productExceptSelf(array, n); for ( int i = 0 ; i < n; i++) { System.out.print(ans[i] + " " ); } } } // This code is contributed by Kapil Kumar (kapilkumar2001) |
蟒蛇3
# Python3 program for the above approach def productExceptSelf(a, n): prod = 1 flag = 0 for i in range (n): # Counting number of elements # which have value # 0 if (a[i] = = 0 ): flag + = 1 else : prod * = a[i] # Creating a new array of size n arr = [ 0 for i in range (n)] for i in range (n): # If number of elements in # array with value 0 # is more than 1 than each # value in new array # will be equal to 0 if (flag > 1 ): arr[i] = 0 # If no element having value # 0 than we will # insert product/a[i] in new array elif (flag = = 0 ): arr[i] = (prod / / a[i]) # If 1 element of array having # value 0 than all # the elements except that index # value , will be # equal to 0 elif (flag = = 1 and a[i] ! = 0 ): arr[i] = 0 # If(flag == 1 && a[i] == 0) else : arr[i] = prod return arr # Driver Code n = 5 array = [ 10 , 3 , 5 , 6 , 2 ] ans = productExceptSelf(array, n) print ( * ans) # This code is contributed by rag2127 |
C#
using System; public class GFG{ public static long [] productExceptSelf( int [] a, int n) { long prod = 1; long flag = 0; // product of all elements for ( int i = 0; i < n; i++) { // counting number of elements // which have value // 0 if (a[i] == 0) flag++; else prod *= a[i]; } // creating a new array of size n long [] arr = new long [n]; for ( int i = 0; i < n; i++) { // if number of elements in // array with value 0 // is more than 1 than each // value in new array // will be equal to 0 if (flag > 1) { arr[i] = 0; } // if no element having value // 0 than we will // insert product/a[i] in new array else if (flag == 0) arr[i] = (prod / a[i]); // if 1 element of array having // value 0 than all // the elements except that index // value , will be // equal to 0 else if (flag == 1 && a[i] != 0) { arr[i] = 0; } // if(flag == 1 && a[i] == 0) else arr[i] = prod; } return arr; } // Driver Code static public void Main (){ int n = 5; int [] array = { 10, 3, 5, 6, 2 }; long [] ans = new long [n]; ans = productExceptSelf(array, n); for ( int i = 0; i < n; i++) { Console.Write(ans[i] + " " ); } } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program for the above approach function productExceptSelf(a, n) { let prod = 1; let flag = 0; // Product of all elements for (let i = 0; i < n; i++) { // Counting number of elements // which have value // 0 if (a[i] == 0) flag++; else prod *= a[i]; } // Creating a new array of size n let arr = Array(n).fill(0); for (let i = 0; i < n; i++) { // If number of elements in // array with value 0 // is more than 1 than each // value in new array // will be equal to 0 if (flag > 1) { arr[i] = 0; } // If no element having value // 0 than we will // insert product/a[i] in new array else if (flag == 0) arr[i] = (prod / a[i]); // If 1 element of array having // value 0 than all // the elements except that index // value , will be // equal to 0 else if (flag == 1 && a[i] != 0) { arr[i] = 0; } // If(flag == 1 && a[i] == 0) else arr[i] = prod; } return arr; } // Driver code let n = 5; let array = [ 10, 3, 5, 6, 2 ]; let ans = Array(n).fill(0); ans = productExceptSelf(array, n); for (let i = 0; i < n; i++) { document.write(ans[i] + " " ); } // This code is contributed by avijitmondal1998 </script> |
输出
180 600 360 300 900
时间复杂度：O（n）
空间复杂性：O（1）
原始数组只需要遍历一次，因此空间复杂度是恒定的。
?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p 一个乘积数组谜题|集2（O（1）空间） 相关问题： 从数组中除同一索引中的元素外的所有元素的异或构造数组 如果您发现上述代码/算法不正确，请写评论，或者找到更好的方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
