Python程序：求使首尾元素对和相等的所需操作次数

假设我们有一个名为nums的数字列表。此列表的长度为偶数。现在考虑一个操作，我们选择nums中的任何数字，并将其更新为[1和nums的最大值]范围内的值。我们必须找到所需此类操作的最小数量，以便对于每个i，nums[i] + nums[n-1-i]等于相同的数字。

因此，如果输入类似于nums = [8,6,2,5,9,2]，则输出将为2，因为如果我们将nums[2]中的第一个2更改为5，并将nums[4]中的9更改为4，则元素将为[8,6,5,5,4,2]，则每个i的nums[i] + nums[n-1-i]将为(8+2) = (6+4) = (5+5) = 10。

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

  • N := nums的大小
  • mx := nums的最大值
  • events := 一个新的列表
  • idx := 0
  • 当 idx < floor(N / 2) 时，执行：
    • a := nums[idx]
    • b := nums[N - idx - 1]
    • 在events的末尾插入一对(min(a + 1, b + 1), 1)
    • 在events的末尾插入一对(a + b, 1)
    • 在events的末尾插入一对(a + b + 1, -1)
    • 在events的末尾插入一对(max(a + mx, b + mx + 1), -1)
    • idx := idx + 1
  • 对列表events进行排序
  • current := 0
  • mx_same := 0
  • 对于events中的每一对(event, delta)，执行：
    • current := current + delta
    • mx_same := max(current, mx_same)
  • 返回 N - mx_same

示例

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

def solve(nums):
   N = len(nums)
   mx = max(nums)
   events = []

   idx = 0
   while idx < N // 2:
      a = nums[idx]
      b = nums[N - idx - 1]

      events.append((min(a + 1, b + 1), 1))
      events.append((a + b, 1))
      events.append((a + b + 1, -1))
      events.append((max(a + mx, b + mx) + 1, -1))

   idx += 1

   events.sort()
   current = 0
   mx_same = 0

   for event, delta in events:
      current += delta
      mx_same = max(current, mx_same)

   return N - mx_same

nums = [8,6,2,5,9,2]
print(solve(nums))

输入

[6, 8, 5, 2, 3]

输出

2

更新于：2021年10月18日

61 次浏览

启动你的职业生涯

完成课程获得认证

开始学习
广告