在 Python 中寻找最小移动以使数组互补的程序

假设我们有一个偶数长度的数组 nums 另一个值限制。一步，我们可以将 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

示例

让我们看看以下实现以获得更好的理解 -

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