题目描述

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

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

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

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

样例

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

输出： 6

解释：

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

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

输出： 3

解释：

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

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

算法

(排序，贪心) $O(n \log n)$

1. 将数组从小到大排序，将第一个数字修改为 $nums(0) - k$，并用一个变量 $p$ 记录上一个数字的值，代表上一个尽可能小的值。
2. 如果 $nums(i) + k <= p$，则这个数字无法再进行修改为不同元素。否则，答案累加 1，$p$ 修改为 $\max(p + 1, nums(i) - k)$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 排序后，遍历数组一次。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(\log n)$ 的额外空间存储排序的系统栈。

C++ 代码

#define LL long long

class Solution {
public:
    int maxDistinctElements(vector<int>& nums, int k) {
        const int n = nums.size();

        sort(nums.begin(), nums.end());

        int ans = 1, p = nums[0] - k;
        for (int i = 1; i < n; i++)
            if (nums[i] + k > p) {
                ++ans;
                p = max(p + 1, nums[i] - k);
            }

        return ans;
    }
};