2025-07-09：使数组元素互不相同所需的最少操作次数。用go语言，给定一个整数数组 nums 和一个整数 k，对于数组中的

福大大架构师每日一题

发布于 2025-07-09 09:15:18

3350

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. 排序数组：
- • 首先将数组 nums 进行升序排序。排序的目的是为了能够有序地处理每个元素，便于调整时避免冲突。
2. 初始化变量：
- • 定义一个变量 pre 来记录前一个调整后的值，初始时设置为 math.MinInt（即最小的整数，确保第一个元素可以自由调整）。
- • 定义一个变量 ans 来记录不同元素的数量，初始为 0。
3. 遍历排序后的数组：
- • 对于每个元素 x，我们需要找到一个调整后的值 x'，使得 x' 满足以下条件：
  - • x' 在 [x - k, x + k] 的范围内。
  - • x' 大于 pre（即前一个调整后的值），以确保 x' 是一个新的唯一值。
- • 具体调整方法：
  - • 计算 x 可以调整的最小值 x - k 和最大值 x + k。
  - • 为了确保 x' 大于 pre，x' 的最小可能值是 pre + 1。
  - • 因此，x' 的候选范围是 [max(x - k, pre + 1), x + k]。
  - • 为了使 x' 尽可能小（以便后续元素有更多调整空间），选择 x' = max(x - k, pre + 1)。
  - • 如果 x' 超出 x + k，则无法调整（即无法满足 x' > pre），此时跳过该元素（不增加 ans）。
  - • 否则，将 x' 作为当前元素的调整值，并更新 pre = x'，同时 ans 增加 1。
4. 边界情况处理：
- • 如果 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. 遍历：
- • x = 1：
  - • x' = max(1 - 2, pre + 1) = max(-1, math.MinInt + 1) = -1。
  - • -1 在 [1 - 2, 1 + 2] = [-1, 3] 范围内。
  - • 更新 pre = -1, ans = 1。
- • x = 2：
  - • x' = max(2 - 2, -1 + 1) = max(0, 0) = 0。
  - • 0 在 [0, 4] 范围内。
  - • 更新 pre = 0, ans = 2。
- • x = 2：
  - • x' = max(2 - 2, 0 + 1) = max(0, 1) = 1。
  - • 1 在 [0, 4] 范围内。
  - • 更新 pre = 1, ans = 3。
- • x = 3：
  - • x' = max(3 - 2, 1 + 1) = max(1, 2) = 2。
  - • 2 在 [1, 5] 范围内。
  - • 更新 pre = 2, ans = 4。
- • x = 3：
  - • x' = max(3 - 2, 2 + 1) = max(1, 3) = 3。
  - • 3 在 [1, 5] 范围内。
  - • 更新 pre = 3, ans = 5。
- • x = 4：
  - • x' = max(4 - 2, 3 + 1) = max(2, 4) = 4。
  - • 4 在 [2, 6] 范围内。
  - • 更新 pre = 4, ans = 6。
4. 最终 ans = 6。

时间复杂度和空间复杂度

1. 时间复杂度：
- • 排序数组的时间复杂度为 O(n log n)，其中 n 是数组长度。
- • 遍历数组的时间复杂度为 O(n)。
- • 因此，总的时间复杂度为 O(n log n)。
2. 空间复杂度：
- • 排序的原地排序（如快速排序）的空间复杂度为 O(log n)（递归栈空间）。
- • 其他变量（如 pre, ans）的空间复杂度为 O(1)。
- • 因此，总的额外空间复杂度为 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)