题目描述
给你一个长度为 偶数 n
的整数数组 nums 和一个整数limit
。每一次操作,你可以将 nums
中的任何整数替换为1
到limit
之间的另一个整数。
如果对于所有下标 i
(下标从 0
开始),nums[i] + nums[n - 1 - i]
都等于同一个数,则数组 nums
是 互补的 。例如,数组 [1,2,3,4] 是互补的,因为对于所有下标i
,nums[i] + nums[n - 1 - i] = 5
。
返回使数组 互补 的 最少操作次数。
样例
示例1
输入:nums = [1,2,4,3], limit = 4
输出:1
解释:经过 1 次操作,你可以将数组 nums 变成 [1,2,2,3](加粗元素是变更的数字):
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.
对于每个 i ,nums[i] + nums[n-1-i] = 4 ,所以 nums 是互补的。
示例2
输入:nums = [1,2,2,1], limit = 2
输出:2
解释:经过 2 次操作,你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ,因为 3 > limit
示例3
输入:nums = [1,2,1,2], limit = 2
输出:0
解释:nums 已经是互补的。
提示:
n == nums.length
2 <= n <= 10^5
1 <= nums[i] <= limit <= 10^5
n
是偶数。
算法1
(差分) $O(max(n, limit))$
大家可以移步 @WZC的题解
算法2
(数学,枚举) $O(max(nlog(n), limit*log(n)))$
- 考虑数字对 $a_1$和$a_2$,和为
s
. - 我们不需要做任何改动,就可以形成和为
s
的一个对。 - 我们尝试找出区间
[l, r]
,使得 $a_1$和$a_2$可以只经过1
次改动就进入这个区间- $l = min(a_1, a_2) + 1$
- $r = max(a_1, a_2) + limit$
记录l
和r
存入两个数组mins
和maxs
- 对于每一个可能的和
t
, $t\in[2, limit * 2] $,mins
中超过t
的以及maxs
中小于t
的情况,(变化一次还不够小,或者变化一次还不够大)表示需要两次变化, 计算对于t
需要两次变化的对数cnt2
。 - 需要一次变化的对数
cnt1
=n/2
- 和等于t
的对数 - 需要进行两次变化的对数(cnt2
) - 考虑对
mins
和max
排序,以通过二分在$log(n)$的时间复杂度内找到cnt2
. - 当前
t
需要cnt1 + cnt2
次变化可以令数组互补。 更新最小的变化次数ans
. - 从
[2, limit * 2]
枚举所有可能的和,统计出可以构造所有和需要的最小操作步数即为答案.
时间复杂度
- 统计
t
,mins
和maxs
需要$O(n)$的时间复杂度 - 对
mins
和maxs
排序需要$O(nlog(n))$的时间复杂度 - 从
[2, limit * 2]
枚举所有可能的和,需要$limit$此操作,每次需要$log(n)$的时间二分mins
和maxs
数组来找到cnt2
和计算cnt1
- 故总时间复杂度为 $O(max(nlog(n), limit*log(n)))$
C++ 代码
const int N = 1e5 + 10;
int sumDict[N * 2];
int mins[N / 2], maxs[N / 2];
class Solution {
public:
int n;
int minMoves(vector<int>& nums, int limit) {
memset(sumDict, 0,sizeof sumDict);
n = nums.size();
int cnt = n;
for(int i = 0; i < n/2; i++){
sumDict[nums[i] + nums[n - i - 1]] ++;
mins[i] = min(nums[i], nums[n - i - 1]) + 1;
maxs[i] = max(nums[i], nums[n - i - 1]) + limit;
}
sort(mins, mins + n / 2);
sort(maxs, maxs + n / 2);
for(int i = 2; i <= limit* 2; i++){
int cnt2 = mins + n / 2 - upper_bound(mins, mins + n / 2, i) + lower_bound(maxs, maxs + n / 2, i) - maxs;
int cnt1 = n / 2 - sumDict[i] - cnt2;
cnt = min(cnt, cnt1 + 2 * cnt2);
}
return cnt;
}
};