怎么看网站的服务器,新中国风装修,塑胶加工 技术支持 东莞网站建设,建企业网站哪家好文章目录1. 题目2. 解题1. 题目
给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。 每一次操作#xff0c;你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。
如果对于所有下标 i#xff08;下标从 0 开始#xff09;#xff0c;nums[i] nums[…
文章目录1. 题目2. 解题1. 题目
给你一个长度为 偶数 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 是偶数。来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-moves-to-make-array-complementary 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考吴自华大佬
数对的和的范围 [2, 2*limit]使用差分数组记录 数对的和 在数轴上对应区间的操作次数的增量 类似题目 LeetCode 1094. 拼车 LeetCode 370. 区间加法差分思想 LeetCode 995. K 连续位的最小翻转次数差分思想 LeetCode 732. 我的日程安排表 III差分思想
class Solution {
public:int minMoves(vectorint nums, int limit) {int n nums.size();vectorint delta(2*limit2, 0);//差分数组for(int i 0; i n/2; i){int a min(nums[i], nums[n-1-i]);int b max(nums[i], nums[n-1-i]);delta[2] 2;//初始为2次 [2, a1)delta[1a]--;// sum 1a 时2次。[a1, ab) 需要1次差值-1delta[ab]--;// sum ab 时 不需要操作 0差值 -1delta[ab1]; // [ab1, blimit] 时需要操作1次差值 1 delta[b1limit]; // [blimit1, 2*limit] 时需要操作2次差值1}int presum 0, ans n;for(int i 2; i 2*limit; i) {presum delta[i];ans min(ans, presum);}return ans;}
};360 ms 87.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
