Medium

题目描述

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

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

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

数组的 MEX（最小排斥值） 是数组中缺失的最小非负整数。

  • 例如，[-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，实际上是在改变数字与 value 的商，但余数保持不变。

核心观察：

  1. 通过加减操作，我们可以将任意数字 x 变成与其模 value 同余的任意非负数
  2. 例如：x % value = r，那么我们可以将 x 变成 r, r+value, r+2*value, ...

解题思路：

  1. 统计每个数字对 value 取模的余数频次
  2. 对于余数为 r 的数字，我们有 count[r] 个，可以将它们分别变成 r, r+value, r+2*value, ...
  3. 要使 MEX 最大，我们贪心地从 0 开始依次填充：
    • 对于位置 i，如果 count[i % value] > 0，就可以将某个余数为 i % value 的数变成 i
    • 填充后将对应余数的计数减 1
  4. 当某个位置无法填充时，该位置就是最大 MEX

处理负数余数： 在 C++ 等语言中，负数取模可能得到负数，需要调整为正数：((x % value) + value) % value

这个贪心策略是正确的，因为我们总是优先填充较小的位置，这样能保证 MEX 尽可能大。

代码实现

class Solution {
public:
    int findSmallestInteger(vector<int>& nums, int value) {
        vector<int> count(value, 0);
        
        // 统计每个余数的频次
        for (int num : nums) {
            int remainder = ((num % value) + value) % value;
            count[remainder]++;
        }
        
        // 贪心地从0开始填充
        int mex = 0;
        while (count[mex % value] > 0) {
            count[mex % value]--;
            mex++;
        }
        
        return mex;
    }
};

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        # 统计每个余数的频次
        count = [0] * value
        for num in nums:
            remainder = num % value
            count[remainder] += 1
        
        # 贪心地从0开始填充
        mex = 0
        while count[mex % value] > 0:
            count[mex % value] -= 1
            mex += 1
        
        return mex

public class Solution {
    public int FindSmallestInteger(int[] nums, int value) {
        int[] count = new int[value];
        
        // 统计每个余数的频次
        foreach (int num in nums) {
            int remainder = ((num % value) + value) % value;
            count[remainder]++;
        }
        
        // 贪心地从0开始填充
        int mex = 0;
        while (count[mex % value] > 0) {
            count[mex % value]--;
            mex++;
        }
        
        return mex;
    }
}

var findSmallestInteger = function(nums, value) {
    const count = new Array(value).fill(0);
    
    // 统计每个余数的频次
    for (const num of nums) {
        const remainder = ((num % value) + value) % value;
        count[remainder]++;
    }
    
    // 贪心地从0开始填充
    let mex = 0;
    while (count[mex % value] > 0) {
        count[mex % value]--;
        mex++;
    }
    
    return mex;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + k)n 为数组长度，k 为可能的 MEX 值，最坏情况下 k = n
空间复杂度O(value)需要额外数组存储每个余数的频次

相关题目