题目描述
给你一个长度为 n
的整数数组 nums
,n
是 偶数,同时给你一个整数 k
。
你可以对数组进行一些操作。每次操作中,你可以将数组中 任一 元素替换为 0
到 k
之间的 任一 整数。
执行完所有操作以后,你需要确保最后得到的数组满足以下条件:
- 存在一个整数
X
,满足对于所有的(0 <= i < n)
都有abs(a[i] - a[n - i - 1]) = X
。
请你返回满足以上条件 最少 修改次数。
样例
输入:nums = [1,0,1,2,4,3], k = 4
输出:2
解释:
我们可以执行以下操作:
将 nums[1] 变为 2,结果数组为 nums = [1,2,1,2,4,3]。
将 nums[3] 变为 3,结果数组为 nums = [1,2,1,3,4,3]。
整数 X 为 2。
输入:nums = [0,1,2,3,3,6,5,4], k = 6
输出:2
解释:
我们可以执行以下操作:
将 nums[3] 变为 0,结果数组为 nums = [0,1,2,0,3,6,5,4]。
将 nums[4] 变为 4,结果数组为 nums = [0,1,2,0,4,6,5,4]。
整数 X 为 4。
限制
2 <= n == nums.length <= 10^5
n
是偶数。0 <= nums[i] <= k <= 10^5
算法
(思维题,差分数组) $O(n + k)$
- 对于任意一对数字,假设为 $x$ 和 $y$。如果 $X = |x - y|$,则修改代价为 0。
- 其他情况下,如果 $0 \le X \le \max(x, k - x, y, k - y)$,则修改代价为 1。
- 否则,修改代价为 2。
- 遍历每一对数字,在差分数组上标记出当 $X = |x - y|$ 的贡献为 0,但 $X \in [0, \max(x, k - x, y, k - y)]$ 的贡献为 $1$(不含 $|x - y|$)。当 $X \in [\max(x, k - x, y, k - y), k]$ 的贡献为 $2$(不含 $|x - y|$)。
- 求差分数组的前缀和,即得到每个位置的真实贡献总和。
时间复杂度
- 标记差分数组的时间复杂度为 $O(n)$。
- 遍历差分数组,求答案的时间复杂度为 $O(k)$。
- 故总时间复杂度为 $O(n + k)$。
空间复杂度
- 需要 $O(k)$ 的额外空间存储差分数组。
C++ 代码
class Solution {
public:
int minChanges(vector<int>& nums, int k) {
const int n = nums.size();
vector<int> cnt(k + 2, 0);
for (int i = 0, j = n - 1; i < j; i++, j--) {
int x = nums[i], y = nums[j];
int d = max(max(x, k - x), max(y, k - y));
++cnt[0]; ++cnt[d + 1];
int t = abs(x - y);
if (t <= d) {
--cnt[t]; ++cnt[t + 1];
} else {
cnt[t] -= 2; cnt[t + 1] += 2;
}
}
int ans = cnt[0];
for (int i = 1; i <= k; i++) {
cnt[i] += cnt[i - 1];
ans = min(ans, cnt[i]);
}
return ans;
}
};