题目描述
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).
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
Therefore, nums[i] + nums[n-1-i] = 4 for every i, so nums is complementary.
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.
Constraints:
n == nums.length
2 <= n <= 105
1 <= nums[i] <= limit <= 105
n
is even.
算法
(差分数组) $O(limit)$
对于nums[i]
和nums[n - 1 - i]
,始终让nums[n - i - 1] >= nums[i]
,用a
代表nums[i]
, b
代表nums[n - i - 1]
,那么考虑对于只有两个数字的情况下,target
对于结果的影响。首先因为题目限定数据范围1 <= nums[i] <= limit
,所以target
的范围是2 <= target <= limit * 2
。考虑target
落在不同区间上产生的影响:
- 当
2 <= target <= a
时,意味着如果只是修改一个数字,那么这个数字即使被修改成最小的1也无法满足条件,所以target
在区间[2, a]
内,修改次数为2 - 当
a < target < a + b
时,此时只需要修改一个数字,即将b
修改成target - a
即可,所以target
落在区间[a + 1, a + b - 1]
内,修改次数为1 - 当
target = a + b
时,符合题目要求,无需修改 - 当
a + b < target <= b + limit
时,此时只需要修改一个数字,即将a
修改成target - b
即可,所以target
落在区间[a + b + 1, b + limit]
内,修改次数为1 - 当
target > b + limit
时,此时即使把a
修改成limit
也无法满足,所以必须修改两个数字,即target
落在区间[b + limit + 1, limit * 2]
内,修改次数为2
经过上面对于2个元素的分析,发现可以有一种思路是:维护一个数组,其下标代表target
,数组记录为target
时的修改次数,初始化为0。对于nums[i], nums[n - 1 - i]
,按照上面的分析将对应位置加上修改次数,那么遍历完一边数组,从区间[2, 2 * limit]
中找最小值即可。修改可以看成区间修改,遍历数组查询最小值其实相当于单点查询,很显然树状数组或者线段树可以满足,时间复杂度为$O(n \log{n})$。
但是发现上述的区间修改有个特点,就是每次都会修改[2, limit * 2]
整个区间,和以往的只修改一个子区间有差别,类似于标记的思路,用d[i]
代表从第i
个位置开始的每个数字都比nums[i - 1]
要大d[i]
,那么对于将区间[2, a]
都加上2,可以只在2
的位置d[2] += 2
,而[3, a]
都是0,这样起到了等效的作用。实际上这就是差分数组。于是我们可以采取更高效的办法来进行区间修改,每次的修改操作
d[2]
要加2d[a + 1]
要减一d[a + b]
要减一d[a + b + 1]
要加一d[b + limit + 1]
要加一
那么最后求取差分数组的前缀和preSum[i]
其实就是target = i
时的修改次数,此时求取最小值即可。时间复杂度优化到$O(n)$。
C++ 代码
class Solution {
public:
int minMoves(vector<int>& nums, int limit) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n = nums.size();
vector<int> d(2 * limit + 5, 0);
int half = n >> 1;
for (int i = 0; i < half; ++i) {
if (nums[i] > nums[n - 1 - i]) std::swap(nums[i], nums[n - 1 - i]);
int & a = nums[i];
int & b = nums[n - 1 - i];
d[2] += 2;
--d[a + 1];
--d[a + b];
++d[a + b + 1];
++d[b + limit + 1];
}
int res = d[2], cur = res;
for (int i = 3; i <= limit * 2; ++i) {
cur += d[i];
res = min(res, cur);
}
return res;
}
};