Skip to content

Latest commit

 

History

History
247 lines (192 loc) · 6.98 KB

README.md

File metadata and controls

247 lines (192 loc) · 6.98 KB
comments difficulty edit_url rating source tags
true
中等
1996
第 135 场双周赛 Q3
数组
哈希表
前缀和

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

English Version

题目描述

给你一个长度为 n 的整数数组 nums ，n 是 偶数 ，同时给你一个整数 k 。

你可以对数组进行一些操作。每次操作中，你可以将数组中 任一 元素替换为 0 到 k 之间的 任一 整数。

执行完所有操作以后，你需要确保最后得到的数组满足以下条件：

  • 存在一个整数 X ，满足对于所有的 (0 <= i < n) 都有 abs(a[i] - a[n - i - 1]) = X 。

请你返回满足以上条件 最少 修改次数。

 

示例 1：

输入：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 。

示例 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 <= 105
  • n 是偶数。
  • 0 <= nums[i] <= k <= 105

解法

方法一：差分数组

假设最终的数组中，数对 $\textit{nums}[i]$ 和 $\textit{nums}[n-i-1]$ 的差值为 $s$。

我们不妨设 $x$ 为 $\textit{nums}[i]$ 和 $\textit{nums}[n-i-1]$ 的较小值，设 $y$ 为 $\textit{nums}[i]$ 和 $\textit{nums}[n-i-1]$ 的较大值。

对于每一对数，我们有以下几种情况：

  • 如果不需要改动，那么 $y - x = s$。
  • 如果改动一次，那么 $s \le \max(y, k - x)$，最大值就是把 $x$ 变为 $0$，或者把 $y$ 变为 $k$。
  • 如果改动两次，那么 $s \gt \max(y, k - x)$。

即：

  • 在 $[0,y-x-1]$ 范围内，需要改动 $1$ 次。
  • 在 $[y-x]$ 时，不需要改动。
  • 在 $[y-x+1, \max(y, k-x)]$ 范围内，需要改动 $1$ 次。
  • 在 $[\max(y, k-x)+1, k]$ 范围内，需要改动 $2$ 次。

我们枚举每一个数对，利用差分数组，更新每个数对在不同区间范围内的改动次数。

最后，我们求出差分数组的前缀和中的最小值，即为最少的改动次数。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\textit{nums}$ 的长度。

相似题目：

Python3

class Solution:
    def minChanges(self, nums: List[int], k: int) -> int:
        d = [0] * (k + 2)
        n = len(nums)
        for i in range(n // 2):
            x, y = nums[i], nums[-i - 1]
            if x > y:
                x, y = y, x
            d[0] += 1
            d[y - x] -= 1
            d[y - x + 1] += 1
            d[max(y, k - x) + 1] -= 1
            d[max(y, k - x) + 1] += 2
        return min(accumulate(d))

Java

class Solution {
    public int minChanges(int[] nums, int k) {
        int[] d = new int[k + 2];
        int n = nums.length;
        for (int i = 0; i < n / 2; ++i) {
            int x = Math.min(nums[i], nums[n - i - 1]);
            int y = Math.max(nums[i], nums[n - i - 1]);
            d[0] += 1;
            d[y - x] -= 1;
            d[y - x + 1] += 1;
            d[Math.max(y, k - x) + 1] -= 1;
            d[Math.max(y, k - x) + 1] += 2;
        }
        int ans = n, s = 0;
        for (int x : d) {
            s += x;
            ans = Math.min(ans, s);
        }
        return ans;
    }
}

C++

class Solution {
public:
    int minChanges(vector<int>& nums, int k) {
        int d[k + 2];
        memset(d, 0, sizeof(d));
        int n = nums.size();
        for (int i = 0; i < n / 2; ++i) {
            int x = min(nums[i], nums[n - i - 1]);
            int y = max(nums[i], nums[n - i - 1]);
            d[0] += 1;
            d[y - x] -= 1;
            d[y - x + 1] += 1;
            d[max(y, k - x) + 1] -= 1;
            d[max(y, k - x) + 1] += 2;
        }
        int ans = n, s = 0;
        for (int x : d) {
            s += x;
            ans = min(ans, s);
        }
        return ans;
    }
};

Go

func minChanges(nums []int, k int) int {
	d := make([]int, k+2)
	n := len(nums)
	for i := 0; i < n/2; i++ {
		x, y := nums[i], nums[n-1-i]
		if x > y {
			x, y = y, x
		}
		d[0] += 1
		d[y-x] -= 1
		d[y-x+1] += 1
		d[max(y, k-x)+1] -= 1
		d[max(y, k-x)+1] += 2
	}
	ans, s := n, 0
	for _, x := range d {
		s += x
		ans = min(ans, s)
	}
	return ans
}

TypeScript

function minChanges(nums: number[], k: number): number {
    const d: number[] = Array(k + 2).fill(0);
    const n = nums.length;
    for (let i = 0; i < n >> 1; ++i) {
        const x = Math.min(nums[i], nums[n - 1 - i]);
        const y = Math.max(nums[i], nums[n - 1 - i]);
        d[0] += 1;
        d[y - x] -= 1;
        d[y - x + 1] += 1;
        d[Math.max(y, k - x) + 1] -= 1;
        d[Math.max(y, k - x) + 1] += 2;
    }
    let [ans, s] = [n, 0];
    for (const x of d) {
        s += x;
        ans = Math.min(ans, s);
    }
    return ans;
}