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:
[-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 <= 1051 <= nums[i] <= 1090 <= k <= 109class Solution {
public int maxDistinctElements(int[] nums, int k) {
Arrays.sort(nums);
TreeSet<Integer> set = new TreeSet<>();
set.add(Integer.MIN_VALUE);
for (int n : nums)
set.add(Math.min(Math.max(set.last() + 1, n - k), n + k));
set.remove(Integer.MIN_VALUE);
// System.out.println(set);
return set.size();
}
}class Solution {
public int maxDistinctElements(int[] nums, int k) {
Arrays.sort(nums);
int prev = Integer.MIN_VALUE, distinct = 0;
for (int n : nums) {
if (prev == n + k)
continue;
prev = Math.max(prev + 1, n - k);
distinct++;
}
return distinct;
}
}