算法设计（解决乘积数组问题|S2 (使用O(1)空间)） _数据结构

本文概述

C ++
Java
python
C#
的PHP
C ++
Java
Python3
C#

给定一个包含n个整数的数组arr[]，构造一个乘积数组prod[](大小相同)，使prod[i]等于arr[]中除arr[i]之外的所有元素的乘积。在O(n)范围内，不需要除法运算。
例子：

Input: arr[] = {10, 3, 5, 6, 2} Output: prod[] = {180, 600, 360, 300, 900} The elements of output array are {3*5*6*2, 10*5*6*2, 10*3*6*2, 10*3*5*2, 10*3*5*6}Input: arr[] = {1, 2, 1, 3, 4} Output: prod[] = {24, 12, 24, 8, 6} The elements of output array are {3*4*1*2, 1*1*3*4, 4*3*2*1, 1*1*4*2, 1*1*3*2}

在乘积数组问题|S1中已经有一个讨论过的O(n)方法。前面的方法使用额外的O(n)空间来构造product数组。
解决方案1：使用log属性。
【算法设计（解决乘积数组问题|S2 (使用O(1)空间)）】方法：在这篇文章中, 已经讨论了一种更好的方法, 该方法使用log属性查找除特定索引处的数组所有元素的乘积。这种方法不占用额外的空间。
使用log的属性将大数相乘

x = a * b * c * d log(x) = log(a * b * c * d) log(x) = log(a) + log(b) + log(c) + log(d) x = antilog(log(a) + log(b) + log(c) + log(d))

所以这个想法很简单,
遍历数组并找到所有元素的对数和,

log(a[0]) + log(a[1]) + .. + log(a[n-1])

然后再次遍历数组, 并使用该公式查找乘积。

antilog((log(a[0]) + log(a[1]) + .. + log(a[n-1])) - log(a[i]))

这等于除a [i]以外的所有元素的乘积, 即antilog(sumlog(a [i]))。
C ++

// C++ program for product array puzzle // with O(n) time and O(1) space. #include < bits/stdc++.h> using namespace std; // epsilon value to maintain precision #define EPS 1e-9void productPuzzle( int a[], int n) { // to hold sum of all values long double sum = 0; for ( int i = 0; i < n; i++) sum += ( long double ) log10 (a[i]); // output product for each index // antilog to find original product value for ( int i = 0; i < n; i++) cout < < ( int )(EPS + pow (( long double )10.00, sum - log10 (a[i]))) < < " " ; }// Driver code int main() { int a[] = { 10, 3, 5, 6, 2 }; int n = sizeof (a) / sizeof (a[0]); cout < < "The product array is: \n" ; productPuzzle(a, n); return 0; }

Java

// Java program for product array puzzle // with O(n) time and O(1) space. public class Array_puzzle_2 {// epsilon value to maintain precision static final double EPS = 1e- 9 ; static void productPuzzle( int a[], int n) { // to hold sum of all values double sum = 0 ; for ( int i = 0 ; i < n; i++) sum += Math.log10(a[i]); // output product for each index // anti log to find original product value for ( int i = 0 ; i < n; i++) System.out.print( ( int )(EPS + Math.pow( 10.00 , sum - Math.log10(a[i]))) + " " ); }// Driver code public static void main(String args[]) { int a[] = { 10 , 3 , 5 , 6 , 2 }; int n = a.length; System.out.println( "The product array is: " ); productPuzzle(a, n); } } // This code is contributed by Sumit Ghosh

python

# Python program for product array puzzle # with O(n) time and O(1) space.import math# epsilon value to maintain precision EPS = 1e - 9def productPuzzle(a, n):# to hold sum of all values sum = 0 for i in range (n): sum + = math.log10(a[i])# output product for each index # antilog to find original product value for i in range (n): print int ((EPS + pow ( 10.00 , sum - math.log10(a[i])))), return# Driver code a = [ 10 , 3 , 5 , 6 , 2 ] n = len (a) print "The product array is: " productPuzzle(a, n)# This code is contributed by Sachin Bisht

// C# program for product // array puzzle with O(n) // time and O(1) space. using System; class GFG {// epsilon value to // maintain precision static double EPS = 1e-9; static void productPuzzle( int [] a, int n) { // to hold sum of all values double sum = 0; for ( int i = 0; i < n; i++) sum += Math.Log10(a[i]); // output product for each // index anti log to find // original product value for ( int i = 0; i < n; i++) Console.Write(( int )(EPS + Math.Pow(10.00, sum - Math.Log10(a[i]))) + " " ); }// Driver code public static void Main() { int [] a = { 10, 3, 5, 6, 2 }; int n = a.Length; Console.WriteLine( "The product array is: " ); productPuzzle(a, n); } }// This code is contributed by mits

的PHP

< ?php // PHP program for product array puzzle // with O(n) time and O(1) space.// epsilon value to maintain precision $EPS =1e-9; function productPuzzle( $a , $n ) { global $EPS ; // to hold sum of all values $sum = 0; for ( $i = 0; $i < $n ; $i ++) $sum += (double)log10( $a [ $i ]); // output product for each index // antilog to find original product value for ( $i = 0; $i < $n ; $i ++) echo (int)( $EPS + pow((double)10.00, $sum - log10( $a [ $i ]))). " " ; }// Driver code$a = array (10, 3, 5, 6, 2 ); $n = count ( $a ); echo "The product array is: \n" ; productPuzzle( $a , $n ); // This code is contributed by mits ?>

输出如下：

The product array is: 180 600 360 300 900

复杂度分析：

时间复杂度：O(n)。
仅需要两次遍历数组。
空间复杂度：O(1)。
不需要额外的空间。

该方法由Abhishek Rajput提供。
替代方法：这是通过使用pow()函数解决上述问题的另一种方法, 该方法不使用除法并且可以在O(n)时间内工作。
遍历数组并找到数组中所有元素的乘积。将乘积存储在变量中。
然后再次遍历数组, 并使用公式(product * pow(a [i], -1))查找除该数字以外的所有元素的乘积
C ++

// C++ program for product array puzzle // with O(n) time and O(1) space. #include < bits/stdc++.h> using namespace std; // Solve function which prints the answer void solve( int arr[], int n) { // Initialize a variable to store the // total product of the array elements int prod = 1; for ( int i = 0; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for ( int i = 0; i < n; i++) cout < < prod * ( int ) pow ( arr[i], -1) < < " " ; }// Driver Code int main() { int arr[] = { 10, 3, 5, 6, 2 }; int n = sizeof (arr) / sizeof (arr[0]); solve(arr, n); return 0; }// This code is contributed by Sitesh Roy

Java

// Java program for product array puzzle // with O(n) time and O(1) space. public class ArrayPuzzle {static void solve( int arr[], int n) { // Initialize a variable to store the // total product of the array elements int prod = 1 ; for ( int i = 0 ; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for ( int i = 0 ; i < n; i++) System.out.print( ( int )prod * Math.pow(arr[i], - 1 ) + " " ); }// Driver code public static void main(String args[]) { int arr[] = { 10 , 3 , 5 , 6 , 2 }; int n = arr.length; solve(arr, n); } } // This code is contributed by Sitesh Roy

Python3

# Python program for product array puzzle # with O(n) time and O(1) space. def solve(arr, n):# Initialize a variable to store the # total product of the array elements prod = 1 for i in arr: prod * = i# we know x / y mathematically is same # as x*(y to power -1) for i in arr: print ( int (prod * (i * * - 1 )), end = " " )# Driver Code arr = [ 10 , 3 , 5 , 6 , 2 ] n = len (arr) solve(arr, n)# This code is contributed by Sitesh Roy

// C# program for product array puzzle // with O(n) time and O(1) space. using System; class GFG {public class ArrayPuzzle {static void solve( int [] arr, int n) { // Initialize a variable to store the // total product of the array elements int prod = 1; for ( int i = 0; i < n; i++) prod *= arr[i]; // we know x/y mathematically is same // as x*(y to power -1) for ( int i = 0; i < n; i++) Console.Write( ( int )prod * Math.Pow(arr[i], -1) + " " ); }// Driver code static public void Main() { int [] arr = { 10, 3, 5, 6, 2 }; int n = arr.Length; solve(arr, n); } } } // This code is contributed by shivanisinghss2110

输出如下：