Python程序：查找使数组互补所需的最小移动次数

假设我们有一个偶数长度的数组nums和另一个值limit。在一次移动中，我们可以将nums中的任何值替换为1到limit（含）之间的另一个值。如果对于所有索引i，nums[i] + nums[n-1-i]都等于同一个数字，则称该数组是互补的。因此，我们必须找到使nums互补所需的最小移动次数。

因此，如果输入类似于nums = [1,4,2,3] limit = 4，则输出将为1，因为在一个移动中，我们可以将索引1处的元素更改为2，因此数组将为[1,2,2,3]，然后nums[0] + nums[3] = 4，nums[1] + nums[2] = 4，nums[2] + nums[1] = 4，nums[3] + nums[0] = 4

为了解决这个问题，我们将遵循以下步骤：

  • n := nums的大小
  • mid := n/2的商
  • zero_moves := 一个空的整数类型值的映射
  • start := 一个大小为(2 * limit + 1)的数组，并填充为0
  • end := 一个大小为(2 * limit + 1)的数组，并填充为0
  • res := 无穷大
  • 对于范围0到mid - 1的i，执行以下操作：
    • x := nums[i]
    • y := nums[n - 1 - i]
    • zero_moves[x + y] := zero_moves[x + y] + 1
    • 将start[1 + min(x, y)]增加1
    • 将end[limit + max(x, y)]增加1
  • intervals := 0
  • 对于范围2到limit*2的target，执行以下操作：
    • intervals := intervals + start[target]
    • cost := 2 *(mid - intervals) + intervals - zero_moves[target]
    • res := res和cost的最小值
    • intervals := intervals - end[target]
  • 返回res

示例

让我们看看以下实现，以便更好地理解：

from collections import defaultdict
def solve(nums, limit):
   n = len(nums)
   mid = n // 2

   zero_moves = defaultdict(int)

   start = [0] * (2 * limit + 1)
   end = [0] * (2 * limit + 1)
   res = float('inf')
   for i in range(mid):
      x = nums[i]
      y = nums[n - 1 - i]
      zero_moves[x + y] += 1
      start[min(x, y) + 1] += 1
      end[max(x, y) + limit] += 1

   intervals = 0
   for target in range(2, limit * 2 + 1):
      intervals += start[target]
      cost = 2 * (mid - intervals) + intervals - zero_moves[target]
      res = min(res, cost)
      intervals -= end[target]
   return res

nums = [1,4,2,3]
limit = 4
print(solve(nums, limit))

输入

[1,4,2,3], 4

输出

1

更新于： 2021年10月5日

273次浏览

开启您的职业生涯

通过完成课程获得认证

开始
广告