数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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次浏览
广告