2

给出了两个整数数组，我们必须找到将一个数组转换为另一个数组的最小操作数。

操作如下：

如果我们将数组的一个元素减 1，那么所有其他元素都会加 1。

我们必须找到最小数量的此类操作才能将一个数组更改为另一个数组。

示例假设初始数组为 3 2 2
最终数组为 4 5 3

所需的最少操作数为 5。

解释： 3 2 2 -> 2 3 3 -> 3 4 2 -> 2 5 3 -> 3 4 4 -> 4 5 3

4

3 回答 3

3

设 N 为数组的大小，A 和 B。对于 N=1，任何变换都是可能的，步数为 abs(A[0] - B[0])。对于 N=2，每个操作增加一个数字并减少另一个数字。那么对于存在的解决方案，我们必须有 B[1] = A[1] - B[0] + A[0]，并且操作数是 abs(A[0] - B[0]) （或等效绝对（A[1] - B[1]））。

对于 N > 2，考虑数组中所有元素的总和。每一步将一个元素减 1，将 N-1 个元素增加 1。因此总数增加 N-2。

因此，如果可以使用这样的操作将数组 A 转换为数组 B，那么步数将为 (sum(B) - sum(A)) / (N-2)。叫这个T。

操作是通勤的，所以要计算转换是否可能，计算每个元素减少多少次就足够了。如果第 i 个元素减少 n_i 次，则它会增加 T-n_i 次。所以 B[i] = A[i] - n_i + T - n_i，因此 n_i = (A[i] - B[i] + T) / 2。

这就是我们需要的一切：如果 (sum(B) - sum(A)) 可以被 N-2 整除，则存在一个解，并且调用 T = (sum(B) - sum(A) / (N-2)，我们还需要 A[i] - B[i] + T 可以被 2 整除，并且对于每个 i 都是非负的。

请注意，其中没有任何选择：如果存在解决方案，则它在操作的顺序上是唯一的。

于 2013-10-09T17:30:00.327 回答
1

首先将每个元素更改为否定它必须到达每个目标的距离（即从初始数组中减去最终数组中的每个元素）。然后我们只需要得到全 0。

为此，请不断减小最大值（在这里堆可能是个好主意）。一旦所有数字都变为正数，就没有解决方案。

请注意，您不仅需要将数字减一。您可以安全地将它一直减少到 0（如果它是负数，它仍然可以减少 1）或最多(it's value + minimum's value)/2（因此它们会在中间相遇）

并且 2 元素数组[a,b]仅在a = -b.

例子：

对于3 2 2to 4 5 3，我们归一化为3-4 5-2 3-2=-1 -3 -1

然后我们减少-1给我们-2 -2 0
然后我们减少0给我们-1 -1 -1
然后我们减少-1给我们-2 0 0
然后我们减少0给我们-1 -1 1
然后我们减少1给我们0 0 0

我们完成了。

于 2013-10-09T17:41:47.187 回答
0

这非常简单，因为您只询问了最少操作数是多少。由于您不需要通用算法来实际计算沿途的步骤，因此如果您只需检查操作的每个步骤发生的情况，您可以在 O(n) 时间内轻松完成此操作。

首先，请注意当您对其执行操作时，所有元素的总和如何变化。让我们从简单的案例开始，然后转向更复杂的案例。

假设我们有一个大小为 1 的数组 [1]，并且我们对单个元素执行操作。它变为 [0]。因此，每次操作后数组的总和都会增加 -1。

现在假设我们有一个大小为 2, [1, 1] 的数组，我们针对这两个元素中的任何一个执行操作。它将变为 [2, 0] 或 [0, 2]。因此，每次操作，数组的总和都会增加 0。

对于大小为 3 的数组？[1, 1, 1] 在执行以第一个元素为目标的操作后变为 [0, 2, 2]。

也许您可以在这里看到公式，它是数组总和如何变化的概括，它取决于单个变量，即数组的长度！

对于任何给定的数组 A，计算总和变化的公式是：

delta_sum = len(A) - 2

那么我们如何处理这个增量和呢？好吧，如果对您的示例给予足够的关注，您会注意到您得到的数字 5 不仅仅是随机巧合！[4, 5, 3] 的和是 12，[3, 2, 2] 的和是 7。这两个和之间的差是 5。如果你还记得，delta_sum长度为 3 的数组总是+1。那么如果我们只是这样做呢？（蟒蛇示例）

def minOperations(A, B):
    return (sum(B) - sum(A)) / (len(A) - 2)

令人惊讶的是，这个简单的单行语句为大多数数组 A 和 B 提供了正确的答案，len(A) == len(B)即使是像 A=[] 和 B=[] 这样的空数组也会从该函数返回 0，因为 0/-2 是 0。

但是等等……我们的代码有一些问题！我们将一个数字除以len(A) - 2。万一len(A) - 2 == 0呢？不幸的是，如果我们的delta_sum结果为 0，我们将得到一个 ZeroDivisionError！我们如何解决这个问题？我们可以通过简单地为长度为 2 的数组添加一个特殊情况来修复它。

我们本质上想要做的是：

  1. 如果两个数组完全相同，则返回 0。
  2. (B[0] - A[0])如果两个数组的和相同但元素不同，则返回绝对值。
  3. 否则返回None或一些错误，因为没有解决方案是可能的。例如 [1, 1] -> [2, 2] 如评论中所述

我们几乎完成的代码结果如下：

def minOperations(A, B):
    if len(A) == 2: 
        if A == B: 
            return 0
        elif sum(A) == sum(B): 
            return abs(B[0] - A[0]) 
        else:
            return None
    return (sum(B) - sum(A)) / (len(A) - 2)

不幸的是，我们仍然有一些愚蠢的问题需要处理来完善我们的代码。

其中一个问题是您有两个数组 A 和 B，并且完全不可能通过递减操作将 A 转换为 B。

例如，考虑 A = [-1] 和 B = [1] 的情况。仅使用您在问题中描述的递减运算符，就不可能将 A 转换为 B！我们的函数会巧妙地返回'-2。在这种情况下，我们返回负数的操作（这很可能在概念上和实际上都是不可能的），我们可能想要返回None或一些异常/错误。我们可以通过以下代码做到这一点。

result = (sum(B) - sum(A)) / (len(A) - 2)
return result if result >= 0 else None

然后我们还有另一个问题......如果数组 A = [1,2,3,4] 和数组 B = [1,2,3,5] 怎么办？由于我们的 delta_sum 为 2 并且总和的差为 1，我们将返回 1 / 2 整数除法，在 Python 中为 0...所以我们还需要检查我们的结果是否等价于整数，如果不是，我们是返回无效的答案。我们可以通过以下方式做到这一点：

result = float((sum(B) - sum(A))) / (len(A) - 2)
    return int(result) if result >= 0 and result == int(result) else None

为了使您的代码更加健壮，您还可以添加断言检查以确保两个数组的长度在代码开头是相等的。

assert(len(A) == len(B))

我们完成的代码将如下所示：

def minOperations(A, B):
    assert(len(A) == len(B))
    if len(A) == 2: 
        if A == B: 
            return 0
        elif sum(A) == sum(B): 
            return abs(B[0] - A[0]) 
        else:
            return None
    result = float((sum(B) - sum(A))) / (len(A) - 2)
    return int(result) if result >= 0 and result == int(result) else None
于 2013-10-09T21:43:00.237 回答