Easy

题目描述

给定一个整数数组 nums 和一个整数 k，返回不在 nums 中的最小正整数 k 的倍数。

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

解题思路

这道题需要找到不在数组中的最小正整数 k 的倍数。

思路分析：

  1. 哈希集合法（推荐）：将数组元素存入哈希集合，然后从 k 开始逐个检查 k 的倍数，返回第一个不在集合中的倍数。由于约束条件较小，这种方法效率很高。

  2. 排序+二分查找：对数组排序后，对每个 k 的倍数进行二分查找。但在小数据规模下，哈希查找更直接高效。

  3. 直接遍历：对每个 k 的倍数，遍历整个数组检查是否存在。时间复杂度较高，不推荐。

核心算法：

  • 使用哈希集合存储数组元素，实现 O(1) 查找
  • 从 k 开始，依次检查 k, 2k, 3k, ... 是否在集合中
  • 返回第一个不在集合中的倍数

由于约束条件 nums[i] <= 100 且 k <= 100，最坏情况下我们只需要检查有限个倍数就能找到答案。

代码实现

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

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

public class Solution {
    public int MissingMultiple(int[] nums, int k) {
        HashSet<int> numSet = new HashSet<int>(nums);
        
        int multiple = k;
        while (numSet.Contains(multiple)) {
            multiple += k;
        }
        
        return multiple;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var missingMultiple = function(nums, k) {
    const numSet = new Set(nums);
    
    let multiple = k;
    while (numSet.has(multiple)) {
        multiple += k;
    }
    
    return multiple;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m)n 是数组长度，m 是需要检查的倍数个数，最坏情况 m ≈ 100/k
空间复杂度O(n)哈希集合存储数组元素