다른 값 제한이 짝수인 배열 num이 있다고 가정합니다. 한 번의 이동으로 nums의 값을 1과 limit(포함) 사이의 다른 값으로 바꿀 수 있습니다. 모든 인덱스 i에 대해 nums[i] + nums[n-1-i]가 동일한 숫자이면 배열이 상보적이라고 합니다. 따라서 숫자를 보완하는 데 필요한 최소 이동 수를 찾아야 합니다.
따라서 입력이 nums =[1,4,2,3] limit =4와 같으면 한 번의 이동으로 인덱스 1에서 2까지의 요소를 만들 수 있으므로 출력은 1이 됩니다. 따라서 배열은 [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 :=숫자 크기
- 중간 :=n/2의 몫
- zero_moves :=정수 유형 값의 빈 맵
- start :=크기의 배열(2 * limit + 1), 0으로 채우기
- end :=크기의 배열(2 * limit + 1), 0으로 채움
- res :=무한대
- 0에서 중간 - 1 사이의 i에 대해
- x :=숫자[i]
- y :=숫자[n - 1 - i]
- zero_moves[x + y] :=zero_moves[x + y] + 1
- 시작[1 + x, y의 최소값]을 1씩 증가
- 끝[제한 + x, y의 최대값]을 1씩 증가
- 간격:=0
- 범위 2에서 제한*2까지의 대상에 대해 다음을 수행합니다.
- 간격 :=간격 + 시작[대상]
- 비용:=2 *(중간 - 간격) + 간격 - zero_moves[대상]
- res :=최소 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