文章目录
- 题目描述
- 题目简化
- 思路分析
-
- 初始方法
- 优化方法
- 完整代码
题目描述
现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。
给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。
返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。
k 个数字的 平均值 为这些数字求和后再除以 k 。
注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。
示例 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 次数据是什么，平均值都不可能是 6 。
示例 4：
输入：rolls = [1], mean = 3, n = 1
输出：[5]
解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。
题目简化
这题目说的又臭又长，我简化一下题目，就是玩骰子，每次记录下来骰子显示的数。一共玩X次，但其中n次的数据丢了，仅知道 X次 所显示数的平均值mean，让你求出来其中丢失n次的各值是多少，多种组合返回其中一种即可，顺序也可以无视。
思路分析
初始方法
题目给出了总的平均值，我们只需要知道玩了几次骰子，然后乘以平均值就知道总共的数值和，从而知道缺失的那部分的数值和，然后只需要从1开始逐个加1 ，直到这部分的和加到等于缺失的总数值时即可。
拿示例1 来说:
rolls = [1,5,6], mean = 3, n = 4
- 那么 一共就是玩了 3+4 = 7次骰子。
- 总共的数值 就是 7* 3 = 21.
- 缺失部分的总数值就是 21- （1 + 5 +6） = 9
- 缺失的次数是 4次，4次的总数值是9，所以建立数组 res = [1,1,1,1]
- 开始依次加1，直到数组和等于9.。
- 最后 res = [3,2,2,2]
最后记得处理无解的情况，假如缺失的数值总和为15，而题目所给的缺失次数n = 2，此时就算缺失的那两次都显示的6，也只有12个数，无法达到缺失的15，此时无解。相反，如果缺失的数值为2，而缺失的次数为5，如果5次都显示1，也大于缺失的数值2，此时也是无解。
按照上面的思路就可以了。
优化方法
其实在上面的方法中，res的设置不需要全部从1开始。
依旧是上面的那个例子，res的初始值设置可以为 缺失的数值总和 / 缺失的次数。
所以上面的例子 所设置的初始值就是 9 / 4 =2 向下取整。
从 res = [2,2,2,2] 开始逐个加1 直到符合条件。
完整代码
class Solution:def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:rool_sum = len(rolls) + n# rool_sum 总共投了多少次骰子cor_sum = sum(rolls)# cor_sum 现有数值总和num_sum = mean * rool_sum# num_sum 总共的数值和num_miss = num_sum - cor_sum# num_miss 缺失的数总和start_num = num_miss / n# 分配到每一个数的初始值# 处理无解的情况if num_miss > n * 6 or num_miss < n * 1:return []res = [int(start_num)]*nres_sum = sum(res)temp = num_sum - cor_sum - res_sum# temp 还差多少个数 平均加到每一个上面就行了k = 0length = len(res)for z in range(temp):res[z] +=1return res