用 Python 编写程序，查找使数组互补的最小移动次数

pythonserver side programmingprogramming更新于 2025/11/30 8:12:17

假设我们有一个长度为偶数的数组 nums，另一个值为 limit。在一次移动中，我们可以用 1 到 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 := infinity
对于范围为 0 到 mid - 1 的 i，执行
- x := nums[i]
- y := nums[n - 1 - i]
- zero_moves[x + y] := zero_moves[x + y] + 1
- 将 start[1 + x, y 的最小值] 增加 1
- 将 end[limit + x, y 的最大值] 增加 1
intervals := 0
对于范围为 2 到 limit*2 的目标，执行
- 间隔 := 间隔 + 开始[目标]
- 成本 := 2 *(中间 - 间隔) + 间隔 - zero_moves[目标]
- 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))