Medium

题目描述

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

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

  • 给元素加上范围 [-k, k] 内的任意整数。

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

示例 1：

输入：nums = [1,2,2,3,3,4], k = 2
输出：6
解释：
前四个元素执行操作后，nums 变为 [-1, 0, 1, 2, 3, 4]。

示例 2：

输入：nums = [4,4,4,4], k = 1
输出：3
解释：
通过给 nums[0] 加 -1，给 nums[1] 加 1，nums 变为 [3, 5, 4, 4]。

提示：

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

解题思路

这道题的关键在于理解每个元素可以调整到的范围是 [nums[i]-k, nums[i]+k]，我们需要为每个元素分配一个在其调整范围内的值，使得最终的不同元素数量最大。

贪心策略

最优的策略是使用贪心算法：

  1. 首先将数组排序，这样相邻的元素原始值比较接近，便于统一处理
  2. 对于每个元素，尽量选择其调整范围内最小的可用值
  3. 维护一个"下一个可用值"，确保每次分配的值都是不重复的

具体算法

  1. 排序后，对于第一个元素，选择其调整范围的最小值 nums[0]-k
  2. 对于后续元素 nums[i]，其可选范围是 [nums[i]-k, nums[i]+k]
  3. 在这个范围内选择不小于"下一个可用值"的最小值
  4. 如果范围内没有可用值，则跳过该元素
  5. 更新"下一个可用值"为已选值+1

通过这种贪心策略，我们可以确保每个元素都获得其范围内最优的值分配，从而最大化不同元素的数量。时间复杂度主要来自排序操作。

代码实现

class Solution {
public:
    int maxDistinctElements(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        long long nextAvailable = nums[0] - k;
        int count = 1;
        
        for (int i = 1; i < nums.size(); i++) {
            long long minVal = nums[i] - k;
            long long maxVal = nums[i] + k;
            
            if (nextAvailable + 1 <= maxVal) {
                nextAvailable = max((long long)(nextAvailable + 1), minVal);
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def maxDistinctElements(self, nums: List[int], k: int) -> int:
        nums.sort()
        
        next_available = nums[0] - k
        count = 1
        
        for i in range(1, len(nums)):
            min_val = nums[i] - k
            max_val = nums[i] + k
            
            if next_available + 1 <= max_val:
                next_available = max(next_available + 1, min_val)
                count += 1
        
        return count

public class Solution {
    public int MaxDistinctElements(int[] nums, int k) {
        Array.Sort(nums);
        
        long nextAvailable = nums[0] - k;
        int count = 1;
        
        for (int i = 1; i < nums.Length; i++) {
            long minVal = nums[i] - k;
            long maxVal = nums[i] + k;
            
            if (nextAvailable + 1 <= maxVal) {
                nextAvailable = Math.Max(nextAvailable + 1, minVal);
                count++;
            }
        }
        
        return count;
    }
}

var maxDistinctElements = function(nums, k) {
    nums.sort((a, b) => a - b);
    
    let nextAvailable = nums[0] - k;
    let count = 1;
    
    for (let i = 1; i < nums.length; i++) {
        const minVal = nums[i] - k;
        const maxVal = nums[i] + k;
        
        if (nextAvailable + 1 <= maxVal) {
            nextAvailable = Math.max(nextAvailable + 1, minVal);
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
贪心算法O(n log n)O(1)
  • 时间复杂度：O(n log n)，主要来自排序操作，遍历数组为 O(n)
  • 空间复杂度：O(1)，只使用常数级别的额外空间（不考虑排序的空间开销）

相关题目