3397. Maximum Number of Distinct Elements After Operations

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */

本题给我们一个数字数组 nums 以及一个数字 k

我们可以对 nums 的每一个元素进行一次操作，操作内容是可以任意加 [-k ~ k] 的数字到自身

题目要求我们得出经过操作之后可以得到多少个不重复的数组元素

解题思路

假设我们有一个输入是这样的：nums = [1,2,2,3,3,4], k = 2

那么我们可以得知，要让一个数组重复数字最少的话，就要将每个数字变成允许范围内的最小值

具体来说，我们要执行以下步骤：

1. 将 nums 数组按照升序排序；用 curLimit 表示当前元素经过操作后的最大值；用 count 记录没有重复的元素
2. 遍历数组元素
3. 对于每一个 nums[i] ，求 nums[i]-k（代表当前元素可以变成的最小值）
4. 判断 curLimit+1 与 nums[i]-k 谁大
5. 如果 nums[i]-k 大就表示当前位置没有重复元素，可以将 nums[i] 放在这个位置，此时我们需要更新 curLimit ，然后把 count++
6. 如果 curLimit+1 大则代表 nums[i]-k 的位置已经被占据了，我们需要进一步判断，curLimit+1 与 nums[i]+k 谁大
7. 如果 nums[i]+k 大，表示 nums[i] 还有放的位置，我们把它放在 curLimit+1 的位置上（更新 curLimit，count++）
8. 如果 curLimit+1 大，表示当前的元素没办法通过操作变成不重复的元素了，我们直接跳过遍历下个元素去了
9. 遍历结束返回 count

Javascript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var maxDistinctElements = function (nums, k) {
    let count = 0
    let curLimit = -Infinity
    nums.sort((a, b) => a - b)

    for (const num of nums) {
        const minPossibleNum = Math.max(num - k, curLimit + 1)
        if(minPossibleNum > num + k) {
            continue;
        }
        curLimit = minPossibleNum
        count++
    }

    return count
};