3397. Maximum Number of Distinct Elements After Operations

Posted on Edited on In

3397. Maximum Number of Distinct Elements After Operations

Description

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:

1
2
3
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:

1
2
3
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 <= 10^5
  • 1 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

Hints/Notes

Solution

Language: C++

Cleaner solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxDistinctElements(vector<int>& nums, int k) {
        ranges::sort(nums);
        int ans = 0;
        int pre = INT_MIN; // 记录每个人左边的人的位置
        for (int x : nums) {
            x = clamp(pre + 1, x - k, x + k); // min(max(x - k, pre + 1), x + k)
            if (x > pre) {
                ans++;
                pre = x;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int maxDistinctElements(vector<int>& nums, int k) {
        unordered_set<int> count;
        ranges::sort(nums);
        int n = nums.size(), prev = INT_MIN;
        for (int i = 0; i < n; i++) {
            int min_val = nums[i] - k, max_val = nums[i] + k;
            for (int j = max(min_val, prev); j <= max_val; j++) {
                if (!count.contains(j)) {
                    count.insert(j);
                    prev = j + 1;
                    break;
                }
            }
        }
        return count.size();
    }
};