C ++中的产品数组难题？

• Z时代
• 2024-01-10
• 分类：综合

在这里，我们将看到一个与数组有关的有趣问题。有一个包含n个元素的数组。我们必须创建另一个包含n个元素的数组。但是第二个数组的第i个位置将保存第一个数组除第i个元素以外的所有元素的乘积。一个约束是我们不能在该问题中使用除法运算符。

如果我们可以使用除法，运算，则可以通过获取所有元素的乘积轻松地解决此问题，然后将第一个数组的第i个元素除以并将其存储在第二个数组的第i个位置。

在这里，我们通过创建两个单独的数组来解决此问题。左右。left [i]将保存array [i]左边除array [i]之外的所有元素的乘积，right [i]将保存arr [i]右边除arr [i]之外的所有元素的乘积。该解决方案将花费O(n)时间。但这会占用更多空间。

算法

productArray(arr,n)

begin
   define two arrays left and right of size n
   define an array called res of size n
   the first element of left and last element of right is set as 1
   for i in range 1 to n, do
      left[i] = left[i-1] * arr[i-1]
   done
   for i in range n-1 down to 1, do
      right[i] = right[i+1] * arr[i+1]
   done
   for i in range 1 to n, do
      res[i] = left[i] * right[i];
   done
   return res
end

示例

#include<iostream>
using namespace std;
void printArray(int arr[], int n) {
   for(int i = 0; i<n; i++) {
      cout << arr[i] << " ";
   }
   cout << endl;
}
void productArray(int arr[], int product[], int n) {
   //创建左右数组
   int *left = new int[sizeof(int)*n];
   int *right = new int[sizeof(int)*n];
   //将left []的第一个元素和right []的最后一个元素设置为1-
   left[0] = right[n-1] = 1;
   for(int i = 1; i<n; i++) {
      left[i] = left[i-1] * arr[i-1];
   }
   for(int i = n-2; i>=0; i--) {
      right[i] = right[i+1] * arr[i+1];
   }
   //使用左右数组获取产品数组
   for(int i = 0; i<n; i++) {
      product[i] = left[i] * right[i];
   }
}
main() {
   int myArr[7] = {5, 4, 7, 6, 9, 2, 3};
   int resArr[7];
   cout << "Initial Array: ";
   printArray(myArr, 7);
   productArray(myArr, resArr, 7);
   cout << "Final Array: ";
   printArray(resArr, 7);
}

输出结果

Initial Array: 5 4 7 6 9 2 3
Final Array: 9072 11340 6480 7560 5040 22680 15120

以上是 C ++中的产品数组难题？ 的全部内容， 来源链接： utcz.com/z/347350.html