2025-03-06：给定一个长度为 n 的整数组 nums，其中 n 是偶数，同时还有一个整数 k。你可以进行一些操作，每次

福大大架构师每日一题

发布于 2025-03-06 23:30:39

5200

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

2025-03-06：给定一个长度为 n 的整数组 nums，其中 n 是偶数，同时还有一个整数 k。

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

操作结束后，要求数组满足以下条件：存在一个整数 X，使得对于所有的 i (0 <= i < n) 都有 |a[i] - a[n - i - 1]| = X。

请你计算为了满足这个条件，最少需要进行多少次修改。。用go语言，给定一个长度为 n 的整数组 nums，其中 n 是偶数，同时还有一个整数 k。

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

操作结束后，要求数组满足以下条件：存在一个整数 X，使得对于所有的 i (0 <= i < n) 都有 |a[i] - a[n - i - 1]| = X。

请你计算为了满足这个条件，最少需要进行多少次修改。

2 <= n == nums.length <= 100000。

n 是偶数。

0 <= nums[i] <= k <= 100000。

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

答案2025-03-06：

chatgpt[1]

题目来自leetcode3224。

大体步骤如下：

1.对于给定的数组 nums 和整数 k，我们要通过替换数组中的元素，使得数组满足条件：存在一个整数 X，对于所有的 i（0 <= i < n），都有 |a[i] - a[n - i - 1]| = X。

2.我们首先遍历数组的前半部分（0 到 n/2-1），对于每一对元素（nums[i] 和 nums[n-1-i]），我们考虑计算两者之间的差值 x = abs(nums[i] - nums[n-1-i])。

3.根据条件，我们需要找到一个最小的整数 X，使得所有对应元素之间的差值都等于 X。

4.我们使用一个数组 d 来记录对应差值 x 出现的次数，并根据特定区间范围来更新这个数组。

5.最后，我们遍历数组 d，计算累积和，找到最小的修改次数，使得数组满足条件。

6.时间复杂度为 O(n)，空间复杂度为 O(n)。

综上所述，总的时间复杂度为 O(n)，总的额外空间复杂度为 O(n)。这个解决方案通过操作数组元素的方法来满足题目要求，并找出最少需要修改的次数。

Go完整代码如下：

package main

import (
    "fmt"
)

func minChanges(nums []int, k int)int {
    n := len(nums)
    d := make([]int, k+2)
    for i := 0; i < n/2; i++ {
        p, q := nums[i], nums[n-1-i]
        if p > q { // 保证 p <= q
            p, q = q, p
        }
        x := q - p
        mx := max(q, k-p)
        // [0, x-1] 全部 +1：把 q-p 改成小于 x 的，只需要改 p 或 q 中的一个数
        d[0]++
        d[x]--
        // [x+1, mx] 全部 +1：把 q-p 改成大于 x 小于等于 mx 的，也只需要改 p 或 q 中的一个数
        d[x+1]++
        d[mx+1]--
        // [mx+1, k] 全部 +2：把 q-p 改成大于 mx 的，p 和 q 都需要改
        d[mx+1] += 2
    }

    ans := n
    minModify := 0
    for _, v := range d {
        minModify += v
        ans = min(ans, minModify)
    }
    return ans
}

func main() {
    nums := []int{1, 0, 1, 2, 4, 3}
    k := 4
    result := minChanges(nums, k)
    fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

package main

import (
    "fmt"
)

func minChanges(nums []int, k int) int {
    n := len(nums)
    d := make([]int, k+2)
    for i := 0; i < n/2; i++ {
        p, q := nums[i], nums[n-1-i]
        if p > q { // 保证 p <= q
            p, q = q, p
        }
        x := q - p
        mx := max(q, k-p)
        // [0, x-1] 全部 +1：把 q-p 改成小于 x 的，只需要改 p 或 q 中的一个数
        d[0]++
        d[x]--
        // [x+1, mx] 全部 +1：把 q-p 改成大于 x 小于等于 mx 的，也只需要改 p 或 q 中的一个数
        d[x+1]++
        d[mx+1]--
        // [mx+1, k] 全部 +2：把 q-p 改成大于 mx 的，p 和 q 都需要改
        d[mx+1] += 2
    }

    ans := n
    minModify := 0
    for _, v := range d {
        minModify += v
        ans = min(ans, minModify)
    }
    return ans
}

func main() {
    nums := []int{1, 0, 1, 2, 4, 3}
    k := 4
    result := minChanges(nums, k)
    fmt.Println(result)
}