What is the main pattern in this problem?

The main pattern is greedy choice plus invariant validation, where sorting helps maximize the number of distinct elements.

How does sorting help in this problem?

Sorting the array ensures that you can handle the smallest duplicates first, maximizing the chances of creating new distinct elements.

How should I decide which elements to modify?

Focus on the most frequent elements and modify them first, using either addition or subtraction to create distinct values.

What is the time complexity of this solution?

The time complexity is O(n log n) due to sorting, followed by a linear pass to apply operations and track distinct elements.

What if k is very large?

Even with large k, the greedy approach remains valid, as long as the number of operations is limited to creating distinct values efficiently.

#3397

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

执行操作后不同元素的最大数量

给你一个整数数组 nums 和一个整数 k 。你可以对数组中的每个元素最多执行一次以下操作：将一个在范围 [-k, k] 内的整数加到该元素上。返回执行这些操作后， nums 中可能拥有的不同元素的最大数量。示例 1：输入： nums = [1,2,2,3,3,4], k = …

数组贪心排序

题目描述

给你一个整数数组 nums 和一个整数 k。

你可以对数组中的每个元素最多执行一次以下操作：

将一个在范围 [-k, k] 内的整数加到该元素上。

返回执行这些操作后，nums 中可能拥有的不同元素的最大数量。

示例 1：

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

输出： 6

解释：

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

示例 2：

输入： nums = [4,4,4,4], k = 1

输出： 3

解释：

对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

提示：

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
0 <= k <= 10⁹

lightbulb

解题思路

方法一：贪心 + 排序

我们不妨对数组 $\textit{nums}$ 排序，然后从左到右考虑每个元素 $x$ 。

对于第一个元素，我们可以贪心地将其变为 $x - k$ ，这样可以使得 $x$ 尽可能小，给后续的元素留下更多的空间。我们用变量 $\textit{pre}$ 当前使用到的元素的最大值，初始化为负无穷大。

对于后续的元素 $x$ ，我们可以贪心地将其变为 $\min(x + k, \max(x - k, \textit{pre} + 1))$ 。这里的 $\max(x - k, \textit{pre} + 1)$ 表示我们尽可能地将 $x$ 变得更小，但不能小于 $\textit{pre} + 1$ ，如果存在该值，且小于 $x + k$ ，我们就可以将 $x$ 变为该值，不重复元素数加一，然后我们更新 $\textit{pre}$ 为该值。

遍历结束，我们就得到了不重复元素的最大数量。

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

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def maxDistinctElements(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = 0
        pre = -inf
        for x in nums:
            cur = min(x + k, max(x - k, pre + 1))
            if cur > pre:
                ans += 1
                pre = cur
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of greedy algorithms
question_mark
Ability to optimize operations on duplicates
question_mark
Familiarity with sorting and its impact on optimization

warning

常见陷阱

外企场景

error
Incorrect application of the operation (add or subtract 1) to non-duplicate elements
error
Failing to prioritize duplicates when applying operations
error
Overlooking the need to track distinct elements during modification

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than one operation per element
arrow_right_alt
Considering a larger k value or different operations
arrow_right_alt
Limiting the number of elements that can be modified

help

常见问题

外企场景

继续练习

#3413 收集连续 K 个袋子可以获得的最多硬币数量 #3424 将数组变相同的最小代价 #3362 零数组变换 III