Careercup - Facebook面试题 - 5179916190482432

时间:2023-03-09 18:23:25
Careercup - Facebook面试题 - 5179916190482432

2014-05-01 00:45

题目链接

原题:

input [,,,]
output [,,,] Multiply all fields except it's own position. Restrictions:
. no use of division
. complexity in O(n)

题目:给定一个整数数组,将个元素变为其他元素的乘积,例如[2, 3, 1, 4]变为[12, 8, 24, 6]。限制不准用除法,而且时间复杂度为线性级别。

解法:用一个额外的数组能够完成O(n)时间的算法。由于每个元素在变化之后,应该等于左边和右边的累计乘积,所以两边的累计乘积必须同时能够知道。一边可以用O(1)空间扫描得到,另一边只能用O(n)空间进行记录。时间空间复杂度均为O(n),请看代码。

代码:

 // http://www.careercup.com/question?id=5179916190482432
#include <cstdio>
#include <vector>
using namespace std; void multiplyArray(vector<int> &v)
{
vector<int> vp;
int p;
int i;
int n = (int)v.size(); vp.resize(n);
p = ;
for (i = ; i <= n - ; ++i) {
vp[i] = p;
p *= v[i];
} p = ;
for (i = n - ; i >= ; --i) {
vp[i] = p * vp[i];
p *= v[i];
} for (i = ; i < n; ++i) {
v[i] = vp[i];
} vp.clear();
} int main()
{
int i, n;
vector<int> v; while (scanf("%d", &n) == && n >= ) {
v.resize(n);
for (i = ; i < n; ++i) {
scanf("%d", &v[i]);
}
multiplyArray(v);
for (i = ; i < n; ++i) {
printf((i ? " %d" : "%d"), v[i]);
}
putchar('\n');
} return ;
}