3718. 缺失的最小倍数

题目描述

给你一个整数数组 nums 和一个整数 k，请返回从 nums 中缺失的、最小的正整数 k 的倍数。

倍数指能被 k 整除的任意正整数。

示例 1：

输入： nums = [8,2,3,4,6], k = 2

输出： 10

解释：

当 k = 2 时，其倍数为 2、4、6、8、10、12……，其中在 nums 中缺失的最小倍数是 10。

示例 2：

输入： nums = [1,4,7,10,15], k = 5

输出： 5

解释：

当 k = 5 时，其倍数为 5、10、15、20……，其中在 nums 中缺失的最小倍数是 5。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
1 <= k <= 100

解法

方法一：哈希表 + 枚举

我们先用一个哈希表 \(\textit{s}\) 存储数组 \(\textit{nums}\) 中出现的数字。然后从 \(k\) 的第一个正倍数 \(k \times 1\) 开始，依次枚举每个正倍数，直到找到第一个不在哈希表 \(\textit{s}\) 中出现的倍数，即为答案。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{nums}\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        s = set(nums)
        for i in count(1):
            x = k * i
            if x not in s:
                return x

class Solution {
    public int missingMultiple(int[] nums, int k) {
        boolean[] s = new boolean[101];
        for (int x : nums) {
            s[x] = true;
        }
        for (int i = 1;; ++i) {
            int x = k * i;
            if (x >= s.length || !s[x]) {
                return x;
            }
        }
    }
}

class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        unordered_set<int> s;
        for (int x : nums) {
            s.insert(x);
        }
        for (int i = 1;; ++i) {
            int x = k * i;
            if (!s.contains(x)) {
                return x;
            }
        }
    }
};

func missingMultiple(nums []int, k int) int {
    s := map[int]bool{}
    for _, x := range nums {
        s[x] = true
    }
    for i := 1; ; i++ {
        if x := k * i; !s[x] {
            return x
        }
    }
}

function missingMultiple(nums: number[], k: number): number {
    const s = new Set<number>(nums);
    for (let i = 1; ; ++i) {
        const x = k * i;
        if (!s.has(x)) {
            return x;
        }
    }
}

3718. 缺失的最小倍数

题目描述

解法

方法一：哈希表 + 枚举

评论