0

我有一个算法问题，其中给出了从 1 到 N 的数字，并且要执行许多操作，然后必须在其中找到最小值/最大值。

两个运算 - 加法和减法

和操作的形式是 abcd ，其中 a 是要执行的操作，b 是起始编号，c 是结束编号，d 是要加/减的数字

例如

假设数字是 1 到 N 并且 N = 5

1 2 3 4 5

我们执行操作

1 2 4 5

2 1 3 4

1 4 5 6

通过这些操作，我们将得到从 1 到 N 的数字

1 7 8 9 5

-3 3 4 9 5

-3 3 4 15 11

所以最大值是15，最小值是-3

我的方法：我取了数字的下限和上限，在这种情况下它是 1 和 5 只存储在一个数组中并应用操作，然后找到了最小值和最大值。

有没有更好的方法？

4

2 回答 2

2

我将假设所有更新（加法/减法）操作都发生在找到最大值/最小值之前。对于将更新和最小/最大操作混合在一起，我没有一个好的解决方案。

您可以使用普通数组，其中数组索引 i 处的值是索引 i 和原始数组的索引 (i - 1) 之间的差。这使得从索引 0 到我们数组的索引 i 的总和成为原始数组索引 i 处的值。

减法是与负数的加法，因此可以类似地对待它们。当我们需要从索引 i 到索引 j 的原始数组中添加 k 时，我们会将 k 添加到数组的索引 i，并减去 k 到数组的索引 (j + 1)。每次更新需要 O(1) 时间。

您可以通过累加对值求和并记录最大/最小值来找到原始数组的最小值/最大值。每次操作需要 O(n) 时间。我假设这对整个数组执行一次。

伪代码：

a[N] // Original array
d[N] // Difference array

// Initialization
d[0] = a[0]
for (i = 1 to N-1)
    d[i] = a[i] - a[i - 1]

// Addition (subtraction is similar)
add(from_idx, to_idx, amount) {
    d[from_idx] += amount
    d[to_idx + 1] -= amount
}

// Find max/min for the WHOLE array after add/subtract
current = max = min = d[0];
for (i = 1 to N - 1) {
   current += d[i]; // Sum from d[0] to d[i] is a[i]
   max = MAX(max, current);
   min = MIN(min, current);
}
于 2012-08-06T17:14:33.440 回答
1

一般来说，从性能的角度来看，没有“最好的方法”来找到最小值/最大值，因为它取决于如何使用这个应用程序。

- 在列表中查找最大值和最小值需要 O(n) 时间，因此如果您想运行许多（在输入上下文中的许多）操作，那么在所有操作发生后查找最小值/最大值的方法很好.

-但是如果列表将包含许多元素并且您不想运行那么多操作，则最好检查操作的每个结果是否是新的最大值/最小值，并在必要时进行更新。

于 2012-08-06T16:50:38.667 回答