C ++中的产品数组难题（O(1)空间）？
在这里，我们将看到一个与数组有关的有趣问题。有一个包含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