作者： admin

目标

给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作 numOperations 次。每次操作中，你可以：

• 选择一个下标 i ，它在之前的操作中 没有 被选择过。
• 将 nums[i] 增加范围 [-k, k] 中的一个整数。

在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。

示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1
输出：2
解释：
通过以下操作得到最高频率 2 ：
将 nums[1] 增加 0 。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^5
• 0 <= k <= 10^5
• 0 <= numOperations <= nums.length

思路

对数组 nums 执行 numOperations 次操作，每次操作可以选一个没有被操作过的元素，将其增加 [-k, k] 之间的整数，求元素值的最大出现次数。

对数组排序，并针对元素进行计数，枚举值域范围内的每一个值，二分查找左右 k 范围内的元素个数。

代码

/**
 * @date 2025-10-21 8:53
 */
public class MaxFrequency3346 {

    public int maxFrequency(int[] nums, int k, int numOperations) {
        int max = Arrays.stream(nums).max().getAsInt();
        int[] cnt = new int[max + 1];
        for (int num : nums) {
            cnt[num]++;
        }
        Arrays.sort(nums);
        int res = 1;
        for (int i = 1; i <= max; i++) {
            int l = lowerBound(nums, i - k);
            int r = upperBound(nums, i + k);
            res = Math.max(res, cnt[i] + Math.min(r - l + 1 - cnt[i], numOperations));
        }
        return res;
    }

    public int lowerBound(int[] nums, int target) {
        int r = nums.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (nums[mid] >= target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
            mid = l + (r - l) / 2;
        }
        return l;
    }

    public int upperBound(int[] nums, int target) {
        int r = nums.length - 1;
        int l = 0;
        int mid = l + (r - l) / 2;
        while (l <= r) {
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
            mid = l + (r - l) / 2;
        }
        return r;
    }

}

性能

目标

给你一个整数数组 nums 和一个整数 k。

你可以对数组中的每个元素 最多 执行 一次 以下操作：

• 将一个在范围 [-k, k] 内的整数加到该元素上。

返回执行这些操作后，nums 中可能拥有的不同元素的 最大 数量。

示例 1：

输入： nums = [1,2,2,3,3,4], k = 2
输出： 6
解释：
对前四个元素执行操作，nums 变为 [-1, 0, 1, 2, 3, 4]，可以获得 6 个不同的元素。

示例 2：

输入： nums = [4,4,4,4], k = 1
输出： 3
解释：
对 nums[0] 加 -1，以及对 nums[1] 加 1，nums 变为 [3, 5, 4, 4]，可以获得 3 个不同的元素。

说明：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= k <= 10^9

思路

有一个整数数组 nums，允许对数组中的每个元素加上 [-k, k] 的整数，求操作后数组中不同元素的最大个数。

先对数组进行排序，计算相同元素个数，同时记录前一个元素操作后的最大值 + 1，当前相同元素的个数可以操作变成不同元素的范围是 [Math.max(nums[start] - k, prev), Math.min(nums[start] + k, l + cnt - 1)]。

代码

/**
 * @date 2025-10-20 10:09
 */
public class MaxDistinctElements3397 {

    public int maxDistinctElements(int[] nums, int k) {
        int n = nums.length;
        int i = 0;
        int prev = Integer.MIN_VALUE;
        int res = 0;
        Arrays.sort(nums);
        while (i < n) {
            int start = i;
            while (i < n && nums[i] == nums[start]) {
                i++;
            }
            int cnt = i - start;
            int l = Math.max(nums[start] - k, prev);
            int r = Math.min(nums[start] + k, l + cnt - 1);
            res += r - l + 1;
            prev = r + 1;
        }
        return res;
    }

}

性能

目标

给你一个下标从 0 开始的整数数组 nums 和一个整数 value 。

在一步操作中，你可以对 nums 中的任一元素加上或减去 value 。

• 例如，如果 nums = [1,2,3] 且 value = 2 ，你可以选择 nums[0] 减去 value ，得到 nums = [-1,2,3] 。

数组的 MEX (minimum excluded) 是指其中数组中缺失的最小非负整数。

• 例如，[-1,2,3] 的 MEX 是 0 ，而 [1,0,3] 的 MEX 是 2 。

返回在执行上述操作 任意次 后，nums 的最大 MEX 。

示例 1：

输入：nums = [1,-10,7,13,6,8], value = 5
输出：4
解释：执行下述操作可以得到这一结果：
- nums[1] 加上 value 两次，nums = [1,0,7,13,6,8]
- nums[2] 减去 value 一次，nums = [1,0,2,13,6,8]
- nums[3] 减去 value 两次，nums = [1,0,2,3,6,8]
nums 的 MEX 是 4 。可以证明 4 是可以取到的最大 MEX 。

示例 2：

输入：nums = [1,-10,7,13,6,8], value = 7
输出：2
解释：执行下述操作可以得到这一结果：
- nums[2] 减去 value 一次，nums = [1,-10,0,13,6,8]
nums 的 MEX 是 2 。可以证明 2 是可以取到的最大 MEX 。

说明：

• 1 <= nums.length, value <= 10^5
• -10^9 <= nums[i] <= 10^9

思路

有一个数组，可以执行 任意 次操作，每次操作可以将任意元素加上或者减去 value，求数组中缺失的最小非负整数的最大值。

题目要求返回缺失的最小非负整数，可以从 0 开始枚举每一个整数 target，问题是如何判断数组中是否存在元素 nums[i] + k * value == target。两边同时对 value 取余可得 nums[i] ≡ target (mod value)。

可以对 nums[i] % value 计数，枚举 target 判断是否还剩有同余元素即可。

代码

/**
 * @date 2025-10-16 8:46
 */
public class FindSmallestInteger2598 {

    public int findSmallestInteger(int[] nums, int value) {
        int[] cnt = new int[value];
        for (int num : nums) {
            int rem = num % value;
            rem = rem >= 0 ? rem : rem + value;
            cnt[rem]++;
        }
        int res = 0;
        while (true) {
            int rem = res % value;
            if (cnt[rem] > 0) {
                cnt[rem]--;
            } else {
                return res;
            }
            res++;
        }
    }

}

性能