网站设计风google下载

Every day a Leetcode

题目来源：2028. 找出缺失的观测数据

解法1：模拟

统计当前 m 个元素的总和 curSum = sum(rolls)，总共 m+n 个元素和为 total = (m + n) * mean。

排除 2 种情况：

1. total - curSum > 6 * n：n 个骰子全丢 6 都补不了 total 和 curSum 的差距。
2. total - curSum < 1 * n：n 个骰子的最小点数和为 n，如果 total - curSum 小于 n，说明数据不合法。

我的答案数组的构造方法：

每个骰子先分配 (total - curSum) / n 个点数，再将 (total - curSum) % n 个骰子的点数加 1。

代码：

/** @lc app=leetcode.cn id=2028 lang=cpp** [2028] 找出缺失的观测数据*/// @lc code=start
class Solution
{
public:vector<int> missingRolls(vector<int> &rolls, int mean, int n){int m = rolls.size();int curSum = accumulate(rolls.begin(), rolls.end(), 0);int total = (m + n) * mean;if (total - curSum > 6 * n || total - curSum < 1 * n)return {};vector<int> ans(n, (total - curSum) / n);for (int i = 0; i < (total - curSum) % n; i++)ans[i]++;return ans;}
};
// @lc code=end

结果：

复杂度分析：

时间复杂度：O(m)，其中 m 是数字 rolls 的长度。

空间复杂度：O(n)。