題目描述
這是 LeetCode 上的 2028. 找出缺失的觀測數(shù)據(jù) 墓拜，難度為 中等撮弧。
Tag : 「模擬」姚糊、「構(gòu)造」
現(xiàn)有一份 次投擲單個「六面」骰子的觀測數(shù)據(jù)，骰子的每個面從
到
編號贸辈。觀測數(shù)據(jù)中缺失了
份擎淤，你手上只拿到剩余
次投擲的數(shù)據(jù)秸仙。幸好你有之前計算過的這
次投擲數(shù)據(jù)的平均值。
給你一個長度為 的整數(shù)數(shù)組
rolls 席吴，其中 是第
次觀測的值。同時給你兩個整數(shù)
和
柬姚。
返回一個長度為 的數(shù)組量承，包含所有缺失的觀測數(shù)據(jù)穴店，且滿足這
次投擲的平均值是
。
如果存在多組符合要求的答案卦洽，只需要返回其中任意一組即可斜棚。如果不存在答案弟蚀，返回一個空數(shù)組。
個數(shù)字的 平均值 為這些數(shù)字求和后再除以
昧绣。
注意 是一個整數(shù)，所以
次投擲的總和需要被
整除夜畴。
示例 1：
輸入：rolls = [3,2,4,3], mean = 4, n = 2
輸出：[6,6]
解釋：所有 n + m 次投擲的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 贪绘。
示例 2：
輸入：rolls = [1,5,6], mean = 3, n = 4
輸出：[2,3,2,2]
解釋：所有 n + m 次投擲的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 央碟。
示例 3：
輸入：rolls = [1,2,3,4], mean = 6, n = 4
輸出：[]
解釋：無論丟失的 4 次數(shù)據(jù)是什么，平均值都不可能是 6 亿虽。
示例 4：
輸入：rolls = [1], mean = 3, n = 1
輸出：[5]
解釋：所有 n + m 次投擲的平均值是 (1 + 5) / 2 = 3 洛勉。
提示：
構(gòu)造
根據(jù)題意收毫，我們需要構(gòu)造長度為 的序列
氓涣，使得
和
并集的平均值為
。
由于最終的平均值 已知引润，我們可以直接算得兩序列之和為
。
使用 減去
可得
议慰。我們知道一個長度為
的有效序列的元素和范圍為
（骰子編號為
）别凹，根據(jù)
與
關(guān)系進行分情況討論：
如果
不落在
范圍內(nèi)炉菲，無解坤溃，直接返回空數(shù)組；
如果
落在
: 起始使用
填充
勺鸦，計算兩者差異值
祝旷，并嘗試將
上（該過程一定可以順利進行）嘶窄。
代碼：
class Solution {
public int[] missingRolls(int[] rolls, int mean, int n) {
int m = rolls.length, cnt = m + n;
int t = mean * cnt;
for (int i : rolls) t -= i;
if (t < n || t > 6 * n) return new int[0];
int[] ans = new int[n];
Arrays.fill(ans, t / n);
if (t / n * n < t) {
int d = t - (t / n * n), idx = 0;
while (d-- > 0) ans[idx++]++;
}
return ans;
}
}
- 時間復雜度：
- 空間復雜度：
最后
這是我們「刷穿 LeetCode」系列文章的第 No.2028 篇柄冲，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目漓拾，部分是有鎖題阁最，我們將先把所有不帶鎖的題目刷完速种。
在這個系列文章里面配阵，除了講解解題思路以外示血，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模板瘫拣。
為了方便各位同學能夠電腦上進行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 麸拄。
在倉庫地址里感帅，你可以看到系列文章的題解鏈接地淀、系列文章的相應代碼、LeetCode 原題鏈接和其他優(yōu)選題解帮毁。
更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 合集新基地 ????
本文由mdnice多平臺發(fā)布
