Java&C++题解与拓展——leetcode2028.找出缺失的观测数据【vector学习与使用】

题目要求思路

JavaC++

vector 总结

可以算出丢失的 n n n个值之和 s u m sum sum，然后构造一个加起来恰好得 s u m sum sum的数组res即可【 ∑ i = 0 n r e s [ i ] = s u m sum_{i=0}^nres[i]=sum ∑i=0n​res[i]=sum】。

r e s [ i ] ∈ [ 1 , 6 ] res[i] in [1,6] res[i]∈[1,6]，所以 s u m ∈ [ n , 6 ∗ n ] sum in [n,6*n] sum∈[n,6∗n]，否则无解返回空数组；有解的时候，一定可以构造出一个包含 a a a个 ⌊ s u m n ⌋ lfloorfrac{sum}{n}rfloor ⌊nsum​⌋和 n − a n-a n−a个 ⌊ s u m n ⌋ + 1 lfloorfrac{sum}{n}rfloor + 1 ⌊nsum​⌋+1的结果。那么将res填充为 ⌊ s u m n ⌋ lfloorfrac{sum}{n}rfloor ⌊nsum​⌋，然后计算需要补 1 1 1的数量，也就是 s u m sum sum与 ⌊ s u m n ⌋ ∗ n lfloorfrac{sum}{n}rfloor*n ⌊nsum​⌋∗n的差值 d i s dis dis，将这些 1 1 1加在res的 d i s dis dis个数上。 Java

class Solution {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length, cnt = m + n;
        int sum = mean * cnt;
        for(int i : rolls)
            sum -= i;
        if(sum < n || sum > 6 * n)
            return new int[0];
        int[] res = new int[n];
        //构造结果
        Arrays.fill(res, sum / n);
        //保证整除
        if(sum / n * n < sum) {
            int dis = sum - (sum / n * n), idx = 0;
            while(dis-- > 0)
                res[idx++]++;
        }
        return res;
    }
}

时间复杂度： O ( m + n ) O(m + n) O(m+n)空间复杂度： O ( n ) O(n) O(n) C++

class Solution {
public:
    vector missingRolls(vector& rolls, int mean, int n) {
        int m = rolls.size(), cnt = m + n;
        int sum = mean * cnt;
        for(int i : rolls)
            sum -= i;
        if(sum < n || sum > 6 * n)
            return {};
        //构造结果
        vector res(n, sum / n);
        //保证整除
        if(sum / n * n < sum) {
            int dis = sum - (sum / n * n), idx = 0;
            while(dis-- > 0)
                res[idx++]++;
        }
        return res;
    }
};

时间复杂度： O ( m + n ) O(m + n) O(m+n)空间复杂度： O ( n ) O(n) O(n) vector

学习参考链接前两天刚学习整理过，今天主要是学习一下如何快速插入多个相同的元素。如何添加 c n t cnt cnt个 v a l val val，参考

初始化时直接添加：

std::vector res(cnt, val);

用insert函数

res.insert(res.end(), cnt, val);//在末尾添加

题目思路不难，主要是想好如何构造能整除的答案。