題目描述:
有 n + m 次骰子擲出結果,已知 m 次的結果陣列 rolls 和所有結果的平均值 mean。求 n 次缺失的骰子結果,使得所有 n + m 次的平均值恰好為 mean。若無合法解則回傳空陣列。
解題思路:
n 個骰子的總和:missingSum = mean * (n + m) - sum(rolls)。missingSum 必須滿足 n <= missingSum <= 6 * n。n 個骰子都取 missingSum / n,餘數 missingSum % n 個骰子各多加 1。時間複雜度:O(n + m) — 計算已知總和 O(m),建構結果 O(n)。
空間複雜度:O(n) — 結果陣列大小為 n。
1. Compute knownSum = sum of rolls 2. Compute missingSum = mean * (n + m) - knownSum 3. If missingSum < n or missingSum > 6*n: return [] 4. Set base = missingSum / n, extra = missingSum % n 5. Create result array of n elements, all set to base 6. Add 1 to the first 'extra' elements 7. Return result
貪心逐一分配 O(n):每次為一個骰子分配盡可能接近平均值的數字,同時確保剩餘的骰子仍能湊出合法總和。邏輯稍複雜但結果相同。
隨機化法 O(n):隨機產生骰子值,最後調整使總和吻合。不保證最優分布但可以通過。