C ++中的产品数组难题（O(1)空间）？

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

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

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

在这里，我们通过采用一个温度变量来求解，即找到左部分和右部分的乘积。该值将放入最终数组中。这样就不会占用额外的空间。

算法

productArray(arr,n)

begin
   define an array called res of size n
   fill the res array with 1
   temp := 1
   for i in range 1 to n, do
      res[i] := temp;
      temp := temp * arr[i]
   done
   for i in range n-1 down to 0, do
      res[i] = res[i] * temp
      temp := temp * arr[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 temp = 1;
   for(int i = 0; i<n; i++) {
      product[i] = 1; //set all elements of product as 1
   }
   for(int i = 0; i < n; i++) { //temp variable will hold product of elements on left excluding arr[i]
      product[i] = temp;
      temp *= arr[i];
   }
   temp = 1;
   for(int i = n - 1; i >= 0; i--) { //temp variable will hold product of elements on right excluding arr[i]
      product[i] *= temp;
      temp *= arr[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 ++中的产品数组难题（O(1)空间）？ 的全部内容， 来源链接： utcz.com/z/335142.html

回到顶部