跳转至

3678. 大于平均值的最小未出现正整数

来源第 165 场双周赛 Q1难度简单分数1306

题目描述

给你一个整数数组 nums。

返回 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

解法

方法一：哈希表

思考

要找不在数组中、且严格大于平均值的最小正整数。从 \(\max(1,\lfloor\textit{avg}\rfloor+1)\) 起逐个试探即可，因为缺失的正整数不会太远。

先把数组放进集合，平均值用整除得到下界。若候选已出现则加一，直到不在集合中。

最坏沿值域走一小段，仍与 \(n\) 同阶。

我们用一个哈希表 \(\textit{s}\) 来记录数组 \(\textit{nums}\) 中出现过的元素。

然后，我们计算数组 \(\textit{nums}\) 的平均值 \(\textit{avg}\)，并将答案 \(\textit{ans}\) 初始化为 \(\max(1, \lfloor \textit{avg} \rfloor + 1)\)。

如果 \(\textit{ans}\) 在 \(\textit{s}\) 中出现过，那么我们将 \(\textit{ans}\) 加一，直到 \(\textit{ans}\) 不在 \(\textit{s}\) 中出现过为止。

最后，返回 \(\textit{ans}\) 即可。

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

1
2
3
4
5
6
7
class Solution:
    def smallestAbsent(self, nums: List[int]) -> int:
        s = set(nums)
        ans = max(1, sum(nums) // len(nums) + 1)
        while ans in s:
            ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int smallestAbsent(int[] nums) {
        Set<Integer> s = new HashSet<>();
        int sum = 0;
        for (int x : nums) {
            s.add(x);
            sum += x;
        }
        int ans = Math.max(1, sum / nums.length + 1);
        while (s.contains(ans)) {
            ++ans;
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int smallestAbsent(vector<int>& nums) {
        unordered_set<int> s;
        int sum = 0;
        for (int x : nums) {
            s.insert(x);
            sum += x;
        }
        int ans = max(1, sum / (int) nums.size() + 1);
        while (s.contains(ans)) {
            ++ans;
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func smallestAbsent(nums []int) int {
    s := map[int]bool{}
    sum := 0
    for _, x := range nums {
        s[x] = true
        sum += x
    }
    ans := max(1, sum/len(nums)+1)
    for s[ans] {
        ans++
    }
    return ans
}

1
2
3
4
5
6
7
8
9
function smallestAbsent(nums: number[]): number {
    const s = new Set<number>(nums);
    const sum = nums.reduce((a, b) => a + b, 0);
    let ans = Math.max(1, Math.floor(sum / nums.length) + 1);
    while (s.has(ans)) {
        ans++;
    }
    return ans;
}

评论