1

给定一个大小为 n 的数组 x，构造一个大小为 n 的数组 y，其中yi = sum(a) - xi.

如何在 O(n) 中使用常量空间而不使用减法运算符来完成此操作？我想不通这个。不能使用按位运算来模拟减法。我知道这里的关键是通过使用一些数据结构来增加额外的常量空间，但是如何通过 O(n) 限制来完成呢？制作一个包含所有组合总和的数组，除了xi需要 O(n^2)。

4

2 回答 2

2

所以，我们有数组 x，我们必须创建数组 y。假设我们的数组 x 的大小为 5（仅作为示例）。所以让我们写出 y' 数组的每个元素的值。

y[0] =      + x[1] + x[2] + x[3] + x[4];
y[1] = x[0] +      + x[2] + x[3] + x[4];
y[2] = x[0] + x[1] +      + x[3] + x[4];
y[3] = x[0] + x[1] + x[2]        + x[4];
y[4] = x[0] + x[1] + x[2] + x[3]       ;

你看到这条对角线了吗？它将 y 分为左部分和右部分，其中 yLeft 的每个下一个元素是前一个 yLeft 元素和 x 数组的某个元素的总和。y 右侧部分的情况相同（只是颠倒了）

代码，C#：

var x = new int[] { 4, 6, 2, 4, -2, 4, 0 };
var y = new int[x.Length];

y[0] = 0;
y[y.Length - 1] = 0;

var curYLeft = 0;
for ( int i = 1; i < x.Length; i++ ) {
    curYLeft += x[i - 1];
    y[i] = curYLeft;
}

var curYRight = 0;
for ( int i = x.Length - 1 - 1; i >= 0; i-- ) {
    curYRight += x[i + 1];
    y[i] += curYRight;
}

for ( int i = 0; i < x.Length; i++ ) {
    Console.WriteLine("{0} {1}", x.Sum() - x[i], y[i]);
}
于 2012-12-02T00:55:10.523 回答
2

禁止减法？
不要放弃！要机敏！:-)

a-b = log(exp(a)/exp(b))
a-b = a+b*cos(pi)
a-b = sqrt(2*(a^2+b^2))*cos(atan(1)+atan2(b,a))
于 2012-12-02T03:13:26.903 回答