Leetcode3224. 使差值相等的最少数组改动次数

Every day a Leetcode

题目来源：3224. 使差值相等的最少数组改动次数

解法1：

想一想，什么情况下答案是 0？什么情况下答案是 1？

如果答案是 0，意味着所有 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。

如果答案是 1，意味着有 n/2−1 个 ∣nums[i]−nums[n−1−i]∣ 都等于同一个数 X。我们只需要修改那对不相等的，设这两个数分别为 p=nums[i], q=nums[n−1−i]。

不妨设 p≤q，分类讨论：

• 如果修改 p，那么把 p 改成 0 可以让差值尽量大，此时差值为 q。
• 如果修改 q，那么把 q 改成 k 可以让差值尽量大，此时差值为 k−p。
• 如果 max(q,k−p)≥X，改其中一个数就行。
• 如果 max(q,k−p)<X，p 和 q 两个数都要改。

注意题目保证 n 是偶数。

代码：

/** @lc app=leetcode.cn id=3224 lang=cpp** [3224] 使差值相等的最少数组改动次数*/// @lc code=start
class Solution
{
public:int minChanges(vector<int> &nums, int k){vector<int> cnt(k + 1), cnt2(k + 1);int n = nums.size();for (int i = 0; i < n / 2; i++){int p = nums[i], q = nums[n - 1 - i];if (p > q){ // 保证 p <= qswap(p, q);}cnt[q - p]++;cnt2[max(q, k - p)]++;}int ans = n;int sum2 = 0; // 统计有多少对 (p,q) 都要改for (int x = 0; x <= k; x++){// 其他 n/2-cnt[x] 对 (p,q) 至少要改一个数，在此基础上，有额外的 sum2 对 (p,q) 还要再改一个数ans = min(ans, n / 2 - cnt[x] + sum2);// 对于后面的更大的 x，当前的这 cnt2[x] 对 (p,q) 都要改sum2 += cnt2[x];}return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(n+k)，其中 n 是数组 nums 的长度。

空间复杂度：O(k)。