算法设计：解决乘积数组问题|S2 (使用O(1)空间)

2021年3月28日15:37:28 发表评论 828 次浏览

本文概述

给定一个包含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属性。

方法：在这篇文章中, 已经讨论了一种更好的方法, 该方法使用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-9
  
void 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 - 9
  
def 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#

// 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#

// 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

输出如下：

180 600 360 300 900

复杂度分析：

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

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: