comments	difficulty	edit_url	rating	source	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3300-3399/3397.Maximum%20Number%20of%20Distinct%20Elements%20After%20Operations/README.md	1687	第 429 场周赛 Q2	贪心 数组 排序

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

English Version

题目描述

给你一个整数数组 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 <= 105
• 1 <= nums[i] <= 109
• 0 <= k <= 109

解法

方法一：贪心 + 排序

我们不妨对数组 $\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}$ 的长度。

Python3

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

Java

class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = 0, pre = Integer.MIN_VALUE;
        for (int x : nums) {
            int cur = Math.min(x + k, Math.max(x - k, pre + 1));
            if (cur > pre) {
                ++ans;
                pre = cur;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maxDistinctElements(vector<int>& nums, int k) {
        ranges::sort(nums);
        int ans = 0, pre = INT_MIN;
        for (int x : nums) {
            int cur = min(x + k, max(x - k, pre + 1));
            if (cur > pre) {
                ++ans;
                pre = cur;
            }
        }
        return ans;
    }
};

Go

func maxDistinctElements(nums []int, k int) (ans int) {
	sort.Ints(nums)
	pre := math.MinInt32
	for _, x := range nums {
		cur := min(x+k, max(x-k, pre+1))
		if cur > pre {
			ans++
			pre = cur
		}
	}
	return
}

TypeScript

function maxDistinctElements(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    let [ans, pre] = [0, -Infinity];
    for (const x of nums) {
        const cur = Math.min(x + k, Math.max(x - k, pre + 1));
        if (cur > pre) {
            ++ans;
            pre = cur;
        }
    }
    return ans;
}