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

每日一题做题记录，参考官方和三叶的题解 【Java&C++题解与拓展——leetcode2028.找出缺失的观测数据【vector学习与使用】】
目录

题目要求
思路
- Java
- C++
- - vector
总结

题目要求
思路可以算出丢失的nnn个值之和sumsumsum，然后构造一个加起来恰好得sumsumsum的数组res即可【∑i=0nres[i]=sum\sum_{i=0}^nres[i]=sum∑i=0n?res[i]=sum】。

res[i]∈[1,6]res[i] \in [1,6]res[i]∈[1,6]，所以sum∈[n,6?n]sum \in [n,6*n]sum∈[n,6?n]，否则无解返回空数组；
有解的时候，一定可以构造出一个包含aaa个?sumn?\lfloor\frac{sum}{n}\rfloor?nsum??和n?an-an?a个?sumn?+1\lfloor\frac{sum}{n}\rfloor + 1?nsum??+1的结果。那么将res填充为?sumn?\lfloor\frac{sum}{n}\rfloor?nsum??，然后计算需要补111的数量，也就是sumsumsum与?sumn??n\lfloor\frac{sum}{n}\rfloor*n?nsum???n的差值disdisdis，将这些111加在res的disdisdis个数上。

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

学习参考链接
前两天刚学习整理过，今天主要是学习一下如何快速插入多个相同的元素。
如何添加cntcntcnt个valvalval，参考
- 初始化时直接添加：
std::vector res(cnt, val);
- 用insert函数
res.insert(res.end(), cnt, val);//在末尾添加

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

欢迎指正与讨论！

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

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