数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究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
更新于：2019 年 7 月 30 日
102 人次观看
广告