j**l
发帖数: 2911 | 1 You are given an array [a1 ... an] and we have to construct another array [
b1 To bn] where bi = a1 * a2 * ... * an / ai. You are allowed to use only
constant
space and the time complexity is O(n). No divisions are allowed.
解法是引入两个辅助数组
Si = a1 * a2 * ... * ai
Ti = ai * a(i+1) * ... * an
则bi = S[i-1] * T[i+1]
但是有题目要求的O(1)空间和O(n)时间的解法么？ |
l******e
发帖数: 6 | 2 1. for (i = 1:n-1)
b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
2. b[0] = b[1];
3. temp = a[0];
4. for (i = 1; i < n; i++)
{
b[i] = temp*b[i+1];
temp *= a[i];
}
Space: temp O(1);
Time: O(n)
【在 j**l 的大作中提到】
: You are given an array [a1 ... an] and we have to construct another array [
: b1 To bn] where bi = a1 * a2 * ... * an / ai. You are allowed to use only
: constant
: space and the time complexity is O(n). No divisions are allowed.
: 解法是引入两个辅助数组
: Si = a1 * a2 * ... * ai
: Ti = ai * a(i+1) * ... * an
: 则bi = S[i-1] * T[i+1]
: 但是有题目要求的O(1)空间和O(n)时间的解法么？
|
f*******e
发帖数: 1161 | 3 牛B！
【在 l******e 的大作中提到】
: 1. for (i = 1:n-1)
: b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
: 2. b[0] = b[1];
: 3. temp = a[0];
: 4. for (i = 1; i < n; i++)
: {
: b[i] = temp*b[i+1];
: temp *= a[i];
: }
: Space: temp O(1);
|
j**l
发帖数: 2911 | 4 原来是要利用输出的数组b缓存辅助数组S和T的结果 |
f*******e
发帖数: 1161 | 5 好像不止这么简单
【在 j**l 的大作中提到】
: 原来是要利用输出的数组b缓存辅助数组S和T的结果
|
r****o
发帖数: 1950 | 6 问问，第1步求b[i]的过程实际上相当于O(n^2)吧。
【在 l******e 的大作中提到】
: 1. for (i = 1:n-1)
: b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
: 2. b[0] = b[1];
: 3. temp = a[0];
: 4. for (i = 1; i < n; i++)
: {
: b[i] = temp*b[i+1];
: temp *= a[i];
: }
: Space: temp O(1);
|
j**l
发帖数: 2911 | 7 可以用例子说明，假如n = 5
首先让b从前向后一重循环累乘并赋值得到b的五个元素如下：
1, a1, a1*a2, a1*a2*a3, a1*a2*a3*a4
然后从后向前一重循环累乘
第五个元素乘1，
第四个元素乘a5
第三个元素乘a5*a4
第二个元素乘a5*a4*a3
第一个元素乘a5*a4*a3*a2 |
j**l
发帖数: 2911 | 8 假定n = 5，数组下标从1开始。
int iter = 1;
int i;
for (i = 1; i <= 5; i++)
{
b[i] = iter;
iter *= a[i];
}
iter = 1;
for (i = 5; i >= 1; i--)
{
b[i] *= iter;
iter *= a[i];
} |
m*****g
发帖数: 226 | 9 niu
【在 l******e 的大作中提到】
: 1. for (i = 1:n-1)
: b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
: 2. b[0] = b[1];
: 3. temp = a[0];
: 4. for (i = 1; i < n; i++)
: {
: b[i] = temp*b[i+1];
: temp *= a[i];
: }
: Space: temp O(1);
|
l******e
发帖数: 6 | 10 不好意思：第一步写错了。应该是：
1. for (i = n - 1; n > 0; i--)
b[i] = a[i]*a[i+1]*a[i+2]*...*a[n];
Sorry for the misleading.
【在 r****o 的大作中提到】
: 问问，第1步求b[i]的过程实际上相当于O(n^2)吧。
|
f****4
发帖数: 1359 | 11 这道题目是求 N个元素数组中 N-1个元素最大积吧？
求连续元素最大乘积的，能用辅助数组解决么？
O(n)的是记录最大，最小乘积 |
l*****a
发帖数: 14598 | 12 you r right.
【在 r****o 的大作中提到】
: 问问，第1步求b[i]的过程实际上相当于O(n^2)吧。
|
d****n
发帖数: 233 | 13 it's O(n) if you do like this:
b[n-1] = a[n-1];
1. for (i = n-2:1)
b[i] = a[i]*b[i+1];
【在 l*****a 的大作中提到】
: you r right.
|
l*****a
发帖数: 14598 | 14 thanks
【在 d****n 的大作中提到】
: it's O(n) if you do like this:
: b[n-1] = a[n-1];
: 1. for (i = n-2:1)
: b[i] = a[i]*b[i+1];
|
