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
执行操作后不同元素的最大数量。
给你一个整数数组 nums 和一个整数 k。你可以对数组中的每个元素 最多 执行 一次 以下操作：
将一个在范围 [-k, k] 内的整数加到该元素上。
返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。
思路
思路是贪心。题目给的是一个 nums 数组和一个整数 k。首先这道题必须要排序，或者需要有一个类似 treemap 的数据结构使得最后的结果有序，否则是不太好判断某个数字是否存在的。这里我选择排序。
对 input 数组排序过后，我们从第一个数字开始判断。这里的思路是需要让每个数字尽量小，这样才能留出更多余地给后面的数字让他们尽量不重复。对于第一个数字 nums[0]，我们可以把它变成 nums[0] - k，这样是最小的。然后我们记录下当前的 pre = nums[0] - k。为什么变量叫 pre 呢？因为我们需要记录前一个数字的值，方便和后面的数字比较。那么对于下一个数字 nums[1]，他需要满足
- 介于 [nums[1] - k, nums[1] + k] 之间
- 大于 pre
- 所以其实是介于 [max(pre + 1, nums[1] - k), nums[1] + k] 之间
如果数字满足这个区间，则说明找到了一个新的不同数字，我们就把 pre 更新为 max(pre + 1, nums[1] - k)，并且结果 count++。如果不满足这个区间，则说明无法找到一个新的不同数字，我们就跳过这个数字，继续下一个数字的判断。
复杂度
时间O(nlogn)，排序的时间复杂度
空间O(1)
代码
Java实现
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;}
}