数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理
社会科学
时尚研究
法律研究C++ 中的产品数组难题？
在此，我们将看到一个与数组相关的有趣问题。有一个包含 n 个元素的数组。我们必须创建另一个包含 n 个元素的数组。但第二个数组的第 i 个位置将保存第一个数组所有元素的乘积，不包括第 i 个元素。并且有一个限制，即我们不能在此问题中使用除法运算符。
如果我们可以使用除法运算，则我们可以轻松解决这个问题，方法是获取所有元素的乘积，然后除以第一个数组的第 i 个元素，并将其存储在第二个数组的第 i 个位置。
我们通过创建两个单独的数组 left 和 right 来解决这个问题。left[i] 将保存数组[i] 左侧所有元素（不包括数组[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) {
//create left right array
int *left = new int[sizeof(int)*n];
int *right = new int[sizeof(int)*n];
//set the first element of left[] and last element of right[] as 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];
}
//get product array using left and right array
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
更新于: 30-7-2019
191 次浏览
广告