感谢你一路上的陪伴

解题步骤#

1. 我们对于每一个容器内的元素I，同样都进行累加和记录，并且计算期望最小值

   1
   int sum = 0;
   2
   bitset<10000> bit;
   3
   for (int i = 0; i < size; i++) {
   4
       sum+=nums[i];
   5
       if (nums[i]>0) //这里要注意的是，我们只记录正半区,因为当adv为负的时候，需要检查的也仅仅只是从1开始的正半区
   6
           bit[nums[i]] = true;
   7
    }
   8
   int adv = sum / size + 1; //这里不+1为平均值的取整数部分，对于期望值而言，无论adv是整数还是小数，都需要比他大然后取整，所以直接在adv上+1则为期望最小值
   

2. 计算偏移量 对于我们要的最终最小值，其结果分为两种情况: 偏移量 = 距离下一个可用的0的距离

   1. 当adv > 0时 先将此时的bit >> adv然后再开始计算偏移量 此时的最终最小值=期望最小值+偏移量
   2. 当adv < 0时 此时的最终最小值=从正整数1开始的偏移量 所以需要跳过bit[0] 则代码如下

   1
   if (adv >0) //第一种情况
   2
            bit >>= adv;
   3
       else { //第二种情况跳过bit[0]
   4
           bit.set(0);
   5
       }
   6
       int result = 0;
   7
       bit = ~bit;
   8
       result += bit._Find_first(); //巧用库函数来获取第一个不为0的值
   9
       return adv > 0 ? result + adv : result;
   

完整代码如下:

1
class Solution {
2
    public:
3
        int smallestAbsent(vector<int>& nums) {
4

5
            int sum = 0;
6
            bitset<10000> bit;
7
            int size = nums.size();
8
            for (int i = 0; i < size; i++) {
9
                sum+=nums[i];
10
                if (nums[i]>0)
11
                    bit[nums[i]] = true;
12
            }
13
            int adv = sum / size + 1;
14
            if (adv >0)
15
                bit >>= adv;
16
            else {
17
                bit.set(0);
18
            }
19
            int result = 0;
20
            bit = ~bit;
21
            result += bit._Find_first();
22
            return adv > 0 ? result + adv : result;
23
        }
24
};

复杂度分析#

• 时间复杂度(N)其中 n 是数组 nums 的长度。遍历数组将元素加入bitset的时间是 O(n)，计算答案时需要遍历的元素个数 < n，因此时间复杂度是 O(n)
• 空间复杂度(K)其中 k 是数组中的值的最大值/8的结果。创建的bitset的大小为k+1