You are given an integer array nums and an integer k.

You are allowed to perform the following operation on each element of the array at most once:

Add an integer in the range [-k, k] to the element.
Return the maximum possible number of distinct elements in nums after performing the operations.

Example 1:
Input: nums = [1,2,2,3,3,4], k = 2
Output: 6

Explanation:
nums changes to [-1, 0, 1, 2, 3, 4] after performing operations on the first four elements.

Example 2:
Input: nums = [4,4,4,4], k = 1
Output: 3

Explanation:
By adding -1 to nums[0] and 1 to nums[1], nums changes to [3, 5, 4, 4].

Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 109

執(zhí)行操作后不同元素的最大數(shù)量。

給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k。

你可以對數(shù)組中的每個元素 最多 執(zhí)行 一次 以下操作：

將一個在范圍 [-k, k] 內(nèi)的整數(shù)加到該元素上。
返回執(zhí)行這些操作后，nums 中可能擁有的不同元素的 最大 數(shù)量。

思路

思路是貪心。題目給的是一個 nums 數(shù)組和一個整數(shù) k。首先這道題必須要排序，或者需要有一個類似 treemap 的數(shù)據(jù)結(jié)構(gòu)使得最后的結(jié)果有序，否則是不太好判斷某個數(shù)字是否存在的。這里我選擇排序。

對 input 數(shù)組排序過后，我們從第一個數(shù)字開始判斷。這里的思路是需要讓每個數(shù)字盡量小，這樣才能留出更多余地給后面的數(shù)字讓他們盡量不重復(fù)。對于第一個數(shù)字 nums[0]，我們可以把它變成 nums[0] - k，這樣是最小的。然后我們記錄下當(dāng)前的 pre = nums[0] - k。為什么變量叫 pre 呢？因為我們需要記錄前一個數(shù)字的值，方便和后面的數(shù)字比較。那么對于下一個數(shù)字 nums[1]，他需要滿足

• 介于 [nums[1] - k, nums[1] + k] 之間
• 大于 pre
• 所以其實是介于 [max(pre + 1, nums[1] - k), nums[1] + k] 之間

如果數(shù)字滿足這個區(qū)間，則說明找到了一個新的不同數(shù)字，我們就把 pre 更新為 max(pre + 1, nums[1] - k)，并且結(jié)果 count++。如果不滿足這個區(qū)間，則說明無法找到一個新的不同數(shù)字，我們就跳過這個數(shù)字，繼續(xù)下一個數(shù)字的判斷。

復(fù)雜度

時間O(nlogn)，排序的時間復(fù)雜度
空間O(1)

代碼

Java實現(xiàn)

class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        Arrays.sort(nums);
        int count = 0;
        int pre = Integer.MIN_VALUE;
        for (int num : nums) {
            int left = num - k;
            int right = num + k;
            int cur = Math.max(pre + 1, left);
            if (cur <= right) {
                count++;
                pre = cur;
            }
        }
        return count;
    }
}