2025-07-09：使数组元素互不相同所需的最少操作次数。用go语言，给定一个整数数组 nums 和一个整数 k，对于数组中的每个元素，你最多可以对其进行一次操作：将一个在区间 [-k, k] 内的整数加到该元素上。请问经过这样的调整后，数组中能够出现的不同元素的最大数量是多少？

1 <= nums.length <= 100000。

1 <= nums[i] <= 1000000000。

0 <= k <= 1000000000。

输入： nums = [1,2,2,3,3,4], k = 2。

输出： 6。

解释：

对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

题目来自力扣3397。

解决思路

为了最大化不同元素的数量，我们需要合理地调整每个元素的值，使得调整后的值尽可能不重复。以下是详细的解决步骤：

1. 排序数组：

o 首先将数组 nums 进行升序排序。排序的目的是为了能够有序地处理每个元素，便于调整时避免冲突。

2. 初始化变量：

o 定义一个变量 pre 来记录前一个调整后的值，初始时设置为 math.MinInt（即最小的整数，确保第一个元素可以自由调整）。

o 定义一个变量 ans 来记录不同元素的数量，初始为 0。

3. 遍历排序后的数组：

o 对于每个元素 x，我们需要找到一个调整后的值 x'，使得 x' 满足以下条件：

o x' 在 [x - k, x + k] 的范围内。

o x' 大于 pre（即前一个调整后的值），以确保 x' 是一个新的唯一值。

o 具体调整方法：

o 计算 x 可以调整的最小值 x - k 和最大值 x + k。

o 为了确保 x' 大于 pre，x' 的最小可能值是 pre + 1。

o 因此，x' 的候选范围是 [max(x - k, pre + 1), x + k]。

o 为了使 x' 尽可能小（以便后续元素有更多调整空间），选择 x' = max(x - k, pre + 1)。

o 如果 x' 超出 x + k，则无法调整（即无法满足 x' > pre），此时跳过该元素（不增加 ans）。

o 否则，将 x' 作为当前元素的调整值，并更新 pre = x'，同时 ans 增加 1。

4. 边界情况处理：

o 如果 k 足够大（即 k * 2 + 1 >= n，其中 n 是数组长度），则可以直接将数组调整为 n 个连续的唯一值（例如 [a, a+1, a+2, ..., a+n-1]），此时最大不同元素数量就是 n。

示例的详细处理过程

以 nums = [1, 2, 2, 3, 3, 4], k = 2 为例：

1. 排序后的数组：[1, 2, 2, 3, 3, 4]。

2. 初始化：pre = math.MinInt, ans = 0。

3. 遍历：

o x = 1：

o x' = max(1 - 2, pre + 1) = max(-1, math.MinInt + 1) = -1。

o -1 在 [1 - 2, 1 + 2] = [-1, 3] 范围内。

o 更新 pre = -1, ans = 1。

o x = 2：

o x' = max(2 - 2, -1 + 1) = max(0, 0) = 0。

o 0 在 [0, 4] 范围内。

o 更新 pre = 0, ans = 2。

o x = 2：

o x' = max(2 - 2, 0 + 1) = max(0, 1) = 1。

o 1 在 [0, 4] 范围内。

o 更新 pre = 1, ans = 3。

o x = 3：

o x' = max(3 - 2, 1 + 1) = max(1, 2) = 2。

o 2 在 [1, 5] 范围内。

o 更新 pre = 2, ans = 4。

o x = 3：

o x' = max(3 - 2, 2 + 1) = max(1, 3) = 3。

o 3 在 [1, 5] 范围内。

o 更新 pre = 3, ans = 5。

o x = 4：

o x' = max(4 - 2, 3 + 1) = max(2, 4) = 4。

o 4 在 [2, 6] 范围内。

o 更新 pre = 4, ans = 6。

4. 最终 ans = 6。

时间复杂度和空间复杂度

1. 时间复杂度：

o 排序数组的时间复杂度为 O(n log n)，其中 n 是数组长度。

o 遍历数组的时间复杂度为 O(n)。

o 因此，总的时间复杂度为 O(n log n)。

2. 空间复杂度：

o 排序的原地排序（如快速排序）的空间复杂度为 O(log n)（递归栈空间）。

o 其他变量（如 pre, ans）的空间复杂度为 O(1)。

o 因此，总的额外空间复杂度为 O(log n)（主要来自排序的栈空间）。如果使用非递归排序，可以优化到 O(1)。

Go完整代码如下：

.

package main

import (
    "fmt"
    "math"
    "slices"
)

func maxDistinctElements(nums []int, k int) (ans int) {
    n := len(nums)
    if k*2+1 >= n {
        return n
    }

    slices.Sort(nums)
    pre := math.MinInt // 记录每个人左边的人的位置
    for _, x := range nums {
        x = min(max(x-k, pre+1), x+k)
        if x > pre {
            ans++
            pre = x
        }
    }
    return
}

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

Python完整代码如下：

.

# -*-coding:utf-8-*-

def max_distinct_elements(nums, k):
    n = len(nums)
    if k * 2 + 1 >= n:
        return n

    nums.sort()
    pre = -10**10  # 用一个很小的数代替 math.MinInt
    ans = 0
    for x in nums:
        candidate = max(x - k, pre + 1)
        x_new = min(candidate, x + k)
        if x_new > pre:
            ans += 1
            pre = x_new
    return ans


if __name__ == "__main__":
    nums = [1, 2, 2, 3, 3, 4]
    k = 2
    result = max_distinct_elements(nums, k)
    print(result)

·

我们相信Go语言和算法为普通开发者提供了困境的“面试利器”，并致力于分享全面的编程知识。在这里，您可以找到最新的Go语言教程、算法解析、提升面试竞争力的秘籍以及行业动态。

欢迎关注“福大规模架构师每日一题”，让 Go 语言和算法助力您的职业发展

·