Medium

题目描述

现有一份 n + m 次投掷单个 6面 骰子的观测数据，骰子的每个面从 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 。

提示：

  • m == rolls.length
  • 1 <= n, m <= 10^5
  • 1 <= rolls[i], mean <= 6

解题思路

这道题的核心是数学推导和合理性检验。

解题思路：

  1. 计算目标总和：由于平均值是 mean，总投掷次数是 n + m，所以总和应该是 total_sum = mean * (n + m)

  2. 计算已知总和：已知的 m 次投掷总和为 known_sum = sum(rolls)

  3. 计算缺失总和：缺失的 n 次投掷的总和应该是 missing_sum = total_sum - known_sum

  4. 合理性检验：

    • 缺失的 n 次投掷，每次最小值是 1，最大值是 6
    • 因此 missing_sum 必须在 [n, 6*n] 范围内，否则无解

  5. 构造答案：

    • 先将所有缺失值都设为 1，这样总和为 n
    • 还需要分配 missing_sum - n 的值
    • 贪心策略：尽量让前面的骰子取更大值（最大6），依次分配剩余值

算法步骤：

  • 初始化结果数组，所有值为 1
  • 计算剩余需要分配的值 remaining = missing_sum - n
  • 从前往后遍历，每个位置最多增加 5（从1变成6）
  • 直到剩余值分配完毕

这种方法时间复杂度是 O(n)，空间复杂度是 O(n)（结果数组）。

代码实现

class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int m = rolls.size();
        int totalSum = mean * (n + m);
        int knownSum = 0;
        for (int roll : rolls) {
            knownSum += roll;
        }
        
        int missingSum = totalSum - knownSum;
        
        // Check if it's possible
        if (missingSum < n || missingSum > 6 * n) {
            return {};
        }
        
        vector<int> result(n, 1);
        int remaining = missingSum - n;
        
        for (int i = 0; i < n && remaining > 0; i++) {
            int add = min(5, remaining);
            result[i] += add;
            remaining -= add;
        }
        
        return result;
    }
};

class Solution:
    def missingRolls(self, rolls: List[int], mean: int, n: int) -> List[int]:
        m = len(rolls)
        total_sum = mean * (n + m)
        known_sum = sum(rolls)
        missing_sum = total_sum - known_sum
        
        # Check if it's possible
        if missing_sum < n or missing_sum > 6 * n:
            return []
        
        result = [1] * n
        remaining = missing_sum - n
        
        for i in range(n):
            if remaining <= 0:
                break
            add = min(5, remaining)
            result[i] += add
            remaining -= add
        
        return result

public class Solution {
    public int[] MissingRolls(int[] rolls, int mean, int n) {
        int m = rolls.Length;
        int totalSum = mean * (n + m);
        int knownSum = rolls.Sum();
        int missingSum = totalSum - knownSum;
        
        // Check if it's possible
        if (missingSum < n || missingSum > 6 * n) {
            return new int[0];
        }
        
        int[] result = new int[n];
        Array.Fill(result, 1);
        int remaining = missingSum - n;
        
        for (int i = 0; i < n && remaining > 0; i++) {
            int add = Math.Min(5, remaining);
            result[i] += add;
            remaining -= add;
        }
        
        return result;
    }
}

var missingRolls = function(rolls, mean, n) {
    const m = rolls.length;
    const totalSum = mean * (n + m);
    const knownSum = rolls.reduce((sum, roll) => sum + roll, 0);
    const missingSum = totalSum - knownSum;
    
    // Check if it's possible
    if (missingSum < n || missingSum > 6 * n) {
        return [];
    }
    
    const result = new Array(n).fill(1);
    let remaining = missingSum - n;
    
    for (let i = 0; i < n && remaining > 0; i++) {
        const add = Math.min(5, remaining);
        result[i] += add;
        remaining -= add;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m + n)，其中 m 是计算已知数组总和的时间，n 是构造结果数组的时间
空间复杂度O(n)，用于存储结果数组（不计算输入和输出占用的空间）

相关题目