Easy

题目描述

给定一个整数数组 nums。

返回 nums 中缺失的最小正整数，且该整数严格大于数组中所有元素的平均值。

数组的平均值定义为所有元素的和除以元素的个数。

示例 1：

输入：nums = [3,5]
输出：6
解释：
nums 的平均值是 (3 + 5) / 2 = 8 / 2 = 4。
大于 4 的最小缺失正整数是 6。

示例 2：

输入：nums = [-1,1,2]
输出：3
解释：
nums 的平均值是 (-1 + 1 + 2) / 3 = 2 / 3 = 0.667。
大于 0.667 的最小缺失正整数是 3。

示例 3：

输入：nums = [4,-1]
输出：2
解释：
nums 的平均值是 (4 + (-1)) / 2 = 3 / 2 = 1.50。
大于 1.50 的最小缺失正整数是 2。

约束条件：

  • 1 <= nums.length <= 100
  • -100 <= nums[i] <= 100

提示：

  • 计算平均值，设 x = floor(avg) + 1（大于平均值的最小整数）
  • 递增 x 直到它不在数组中，然后返回它

解题思路

这道题的核心思路比较直观，可以分为两个步骤：

步骤1：计算平均值的下界 首先计算数组的平均值，然后找到严格大于平均值的最小整数。由于我们要找的是正整数，所以起始值应该是 max(1, floor(average) + 1)。

步骤2：查找缺失的正整数 从起始值开始，逐一检查每个正整数是否在原数组中存在。第一个不存在的正整数就是我们要找的答案。

算法实现：

  1. 计算数组元素的总和和平均值
  2. 确定搜索的起始点：max(1, floor(average) + 1)
  3. 将数组元素存入哈希集合以便快速查找
  4. 从起始点开始递增检查，返回第一个不在集合中的正整数

这种方法时间复杂度为 O(n)，空间复杂度也是 O(n)，其中 n 是数组长度。由于题目约束数组长度最多100，所以这个解法非常高效。

需要注意的边界情况包括：平均值为负数时起始点应该是1，以及确保返回的一定是正整数。

代码实现

class Solution {
public:
    int smallestAbsent(vector<int>& nums) {
        double sum = 0;
        for (int num : nums) {
            sum += num;
        }
        double average = sum / nums.size();
        
        int start = max(1, (int)floor(average) + 1);
        
        unordered_set<int> numSet(nums.begin(), nums.end());
        
        while (numSet.count(start)) {
            start++;
        }
        
        return start;
    }
};

class Solution:
    def smallestAbsent(self, nums: List[int]) -> int:
        average = sum(nums) / len(nums)
        start = max(1, int(average) + 1)
        
        num_set = set(nums)
        
        while start in num_set:
            start += 1
        
        return start

public class Solution {
    public int SmallestAbsent(int[] nums) {
        double sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        double average = sum / nums.Length;
        
        int start = Math.Max(1, (int)Math.Floor(average) + 1);
        
        HashSet<int> numSet = new HashSet<int>(nums);
        
        while (numSet.Contains(start)) {
            start++;
        }
        
        return start;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var smallestAbsent = function(nums) {
    const sum = nums.reduce((acc, num) => acc + num, 0);
    const average = sum / nums.length;
    
    let start = Math.max(1, Math.floor(average) + 1);
    
    const numSet = new Set(nums);
    
    while (numSet.has(start)) {
        start++;
    }
    
    return start;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组计算平均值和构建哈希集合，最坏情况下需要检查的正整数个数有限
空间复杂度O(n)需要额外的哈希集合存储数组元素