문제
You are given an integer array nums of even length n and an integer limit. In one move, you can replace any integer from nums with another integer between 1 and limit, inclusive.
The array nums is complementary if for all indices i (0-indexed), nums[i] + nums[n - 1 - i] equals the same number. For example, the array [1,2,3,4] is complementary because for all indices i, nums[i] + nums[n - 1 - i] = 5.
Return the minimum number of moves required to make nums complementary.
예시
-
Example 1:
- Input: nums = [1,2,4,3], limit = 4 - Output: 1 - Explanation: In 1 move, you can change nums to [1,2,2,3] (underlined elements are changed). -
Example 2:
- Input: nums = [1,2,2,1], limit = 2 - Output: 2 - Explanation: In 2 moves, you can change nums to [2,2,2,2]. You cannot change any number to 3 since 3 > limit. -
Example 3:
- Input: nums = [1,2,1,2], limit = 2 - Output: 0 - Explanation: nums is already complementary.
제한사항
n == nums.length
2 <= n <= 105
1 <= nums[i] <= limit <= 105
n is even.
풀이1
var minMoves = function(N, L) {
let len = N.length,
pfx = new Array(L * 2 + 1).fill(0),
best = 0;
for (let i = len / 2, a, b; i < len; i++) {
(a = N[i]), (b = N[len - i - 1]);
if (b > a) [a, b] = [b, a];
pfx[b]++, pfx[a + b - 1]++, pfx[a + b]--, pfx[a + L]--;
}
for (let i = 1, sum = 0; i <= 2 * L; i++)
(sum += pfx[i]), (best = sum > best ? sum : best);
return len - best;
};그외
첫째, 변경 사항을 저장하기 위해 가능한 쌍 합계의 접두사 배열인 pfx를 만들어야 한다. 그런 다음 N의 쌍을 반복하고 솔루션이 변화하는 값에 대해 pfx를 업데이트합니다.
모든 쌍[a,b]에 대해 두 숫자 중 더 큰 수를 만든다고 합시다. 즉, 최대 범위인 2~2*L의 어느 곳에서나 2회 이동으로 목표를 달성할 수 있습니다. 1회 이동 솔루션은 1+b~a+L까지만 가능합니다. 0 이동 솔루션은 a+b에서만 존재합니다.
pfx를 오름차순의 변경으로 업데이트할 때, 우리는 솔루션이 1+b에서 더 좋아진 다음 a+b+1에서 더 나빠진 다음(-1), 그리고 a+L+1에서 더 나빠진다는 것을 알 수 있다. 목표 수는 2가 되어야 시작하고 변경점 방정식에 +1이 많이 있으므로, 우리는 시간과 공간 효율성을 높이기 위해 모든 것을 1로 줄이고 대신 a, a+b-1, a+b, b+L을 사용함으로써 목표를 약간 단순화할 수 있다.
이제 N의 쌍을 반복한 다음 관련 변경사항으로 pfx의 값을 업데이트할 수 있습니다. 그것이 끝나면, 우리는 pfx를 통해 합계를 내고 저장된 이동에 대한 최상의 값을 찾을 수 있다. 최대 이동 횟수는 렌과 같기 때문에 우리는 그냥 렌 - best를 반납해야 합니다.
다시 풀어야할 문제
