力扣3224.使差值相等的最少数组改动次数

力扣3224.使差值相等的最少数组改动次数

枚举法

• 枚举差值x的数值，max(q,k-p)为修改一个能得到的上限

  • 用cnt存qp差值，cnt2存差值上限
  • 有cnt[x]对无需修改
  • n/2 - cnt[x]对至少修改一个
  • cnt2[0] + cnt[1] + … + cnt2[x-1]需要再修改一个
  • 设sum2 = cnt2[0] + cnt[1] + … + cnt2[x-1]
  • 因此ans = n/2 - cnt[x] + sum2

•   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-i-1];if(p > q)swap(p,q);cnt[q-p] ++;cnt2[max(q,k-p)] ++;}int ans = n;int sum2 = 0;for(int x=0;x<=k;x++){ans = min(ans,n/2 - cnt[x] + sum2);sum2 += cnt2[x];}return ans;}};
  

差分数组

• 对于每一对(q,p)，求出差值x和最大可实现差值mx

  • 他对差值x的贡献为**(0,x-1)修改一次，x不修改，(x+1,mx)修改一次，(mx,k)修改两次**
  • 因此考虑差分数组存每种差值x情况需要修改的次数

•   class Solution {public:int minChanges(vector<int>& nums, int k) {vector<int> d(k+2);int n = nums.size();for(int i=0;i<n/2;i++){int p = nums[i],q = nums[n-i-1];if(p > q)swap(p,q);int x = q - p;int mx = max(q,k - p);//[0,x-1]改一次d[0] ++;d[x] --;//[x,mx]改一次d[x+1] ++;d[mx + 1] --;//[mx,k]改两次d[mx + 1] += 2;}//求前缀和for(int i=0;i<d.size()-1;i++)d[i+1] += d[i];return ranges::min(d);}};