2598. Smallest Missing Non-negative Integer After Operations

Leetcode link

题目简介

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

题目给了一个数字数组 nums 以及一个数字 value

我们可以对数组 nums 的任意数字加或减 value

题目要求我们求出经过无限次操作之后的最大的 MEX

MEX 代表数组从 0 开始遇到的第一个空缺的正整数（比如 [0, 1, 2, 3, 5] 的 MEX 就是 4

解题思路

不难看出对于任何数组元素 num，我们都可以通过无限次加减 value 得到 [0 ~ value-1] 的整数

对于正数 num，我们可以用 num % value 得到

对于负数 num，我们可以用 (value - (-num % value)) % value 得到

如此一来我们可以将数组 nums 转换成一个元素只在 [0 ~ value-1] 范围内的数组 newNums

我们最关心的其实是 newNums 中每个值的个数，所以我们可以用一个长度为 value 的数组 counts 来计算每一个元素的个数

接下来我们只需要计算出 counts 中值最小且下标最小的元素 count（对应到 newNums 出现次数最少且最小的元素）

找到后我们就可以用 count * value + i （i 代表 count 元素的下标）获得最大的 MEX 了

Javascript

/**
 * @param {number[]} nums
 * @param {number} value
 * @return {number}
 */
var findSmallestInteger = function (nums, value) {
    const counts = new Array(value).fill(0)

    nums.forEach(num => {
        if (num < 0) {
            num = value - (-num % value)
        }
        counts[num % value]++
    })

    let res = 0
    let minCountInCounts = Number.MAX_SAFE_INTEGER

    for (let i = 0; i < counts.length; i++) {
        if(counts[i] < minCountInCounts) {
            minCountInCounts = counts[i]
            res = minCountInCounts * value + i
        }
    }

    return res
};