【差分数组】1674. 使数组互补的最少操作次数

本文涉及知识点

差分数组

LeetCode1674. 使数组互补的最少操作次数

给你一个长度为偶数 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⁵
1 <= nums[i] <= limit <= 10⁵
n 是偶数。

差分数组

无论是否修改，nums[i]的值都 $\in$ [1,limit]，故互补后x1=nums[i],x2 =nums[n-1-i], x =x1 + x2，则x $\in$ [2,2limit]。
差分数组vDif[i] 记录 x为i的最少操作次数。vDif[0…1]忽略。
枚举i=0 to n/2-1。
分别求解0次操作的范围，1次操作的范围。2次操作的范围
x1+x2 只需要操作一次
[x1+1,x1+limit] [x2+1,x2+limit] 只需要操作一次。重叠部分需要扣掉。
其它需要两次。
先假定所有都需要两次。
一次或0次操作的返回一次。
0次操作的再返回一次。

代码

核心代码

class Solution {
public:
	int minMoves(vector<int>& nums, int limit) {
		const int n = nums.size();
		vector<int> vDiff(limit * 2 + 2);
		auto Add = [&](int left, int right, int num) {
			vDiff[left] += num;
			vDiff[right + 1] -= num;
		};
		Add(2, limit * 2,n);
		for (int i = 0; i < n / 2; i++) {
			const int x1 = nums[i];
			const int x2 = nums[n - 1 - i];
			Add(x1 + 1, x1 + limit,-1);
			Add(x2 + 1, x2 + limit, -1);
			const int l1 = max(x1 + 1, x2 + 1);
			const int r1 = min(x1 + limit , x2 + limit );
			if (r1 >= l1) {
				Add(l1, r1,1);
			}
			Add(x1 + x2, x1 + x2, -1);
		}
		int sum = 0;
		int ret = n;
		for (int i = 2; i <= 2 * limit; i++) {
			sum += vDiff[i];
			ret = min(ret, sum);
		}
		return ret;
	}
};

测试用例

template<class T1,class T2>
void AssertEx(const T1& t1, const T2& t2)
{
	Assert::AreEqual(t1 , t2);
}

template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{
	Assert::AreEqual(v1.size(), v2.size());	
	for (int i = 0; i < v1.size(); i++)
	{
		Assert::AreEqual(v1[i], v2[i]);
	}
}

template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{
	sort(vv1.begin(), vv1.end());
	sort(vv2.begin(), vv2.end());
	Assert::AreEqual(vv1.size(), vv2.size());
	for (int i = 0; i < vv1.size(); i++)
	{
		AssertEx(vv1[i], vv2[i]);
	}
}

namespace UnitTest
{
	vector<int> nums;
	int limit;
	TEST_CLASS(UnitTest)
	{
	public:
		TEST_METHOD(TestMethod0)
		{
			nums = { 1, 2, 4, 3 }, limit = 4;
			auto res = Solution().minMoves(nums, limit);
			AssertEx(1 ,res);
		}
		TEST_METHOD(TestMethod1)
		{
			nums = { 1,2,2,1 }, limit = 2;
			auto res = Solution().minMoves(nums, limit);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod2)
		{
			nums = { 1,2,1,2 }, limit = 2;
			auto res = Solution().minMoves(nums, limit);
			AssertEx(0, res);
		}
	};
}

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛