LeetCode 解題筆記：3718. Smallest Missing Multiple of K

作者：王一哲
日期：2026年8月25日


LeetCode 題目連結：3718. Smallest Missing Multiple of K

解題想法

簡單題。題目給一個陣列 $nums$ 及一個整數 $k$，要找出不在 $nums$ 之中 $k$ 的倍數最小值。這題可以用集合或是字典記錄 $nums$ 之中的數字；由於測資的範圍不大，也可以用一個長度為 10001 的陣列，將 $nums$ 之中的數字標記為 True。如果用 Python 解題，用 set 及 dict 速度最快；如果用 C 或 C++ 解題，用陣列速度最快。因為答案在 1 到 100 之間，設定一個變數 i，從 1 開始往上線性搜尋就好。

Python 程式碼

set. Runtime: 0 ms, beats 100.00%. Memory: 19.30 MB, beats 18.61%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_set = set(nums)
        i = 1
        while i*k in num_set: i += 1
        return i*k

dict. Runtime: 0 ms, beats 100.00%. Memory: 19.24 MB, beats 53.35%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        num_map = {num: True for num in nums}
        i = 1
        while i*k in num_map: i += 1
        return i*k

list. Runtime: 3 ms, beats 20.84%. Memory: 19.17 MB, beats 88.59%.

class Solution:
    def missingMultiple(self, nums: List[int], k: int) -> int:
        state = [False] * 10001
        for num in nums: state[num] = True
        i = 1
        while state[i*k]: i += 1
        return i*k

C++ 程式碼

unordered_set. Runtime: 3 ms, beats 38.06%. Memory: 25.10 MB, beats 45.06%.

class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        unordered_set<int> num_set (nums.begin(), nums.end());
        int i = 1;
        while(num_set.count(i*k) == 1) {
            i++;
        }
        return i*k;
    }
};

unordered_map. Runtime: 6 ms, beats 12.42%. Memory: 25.24 MB, beats 24.36%.

class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        unordered_map<int, bool> num_map;
        for(int num : nums) num_map[num] = true;
        int i = 1;
        while(num_map[i*k]) i++;
        return i*k;
    }
};

array. Runtime: 0 ms, beats 100.00%. Memory: 25.10 MB, beats 45.06%.

class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        bool state[10001] = {false};
        for(int num : nums) state[num] = true;
        int i = 1;
        while(state[i*k]) i++;
        return i*k;
    }
};

C 語言程式碼

array. Runtime: 0 ms, beats 100.00%. Memory: 10.78 MB, beats 7.89%.

int missingMultiple(int* nums, int numsSize, int k) {
    bool state[10001] = {false};
    for(int i = 0; i < numsSize; i++) state[nums[i]] = true;
    int j = 1;
    while(state[j*k]) j++;
    return j*k;
}