LeetCode 题解工作台
两个盒子中球的颜色数相同的概率
桌面上有 2n 个颜色不完全相同的球，球的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。 所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。 注意： 这两个盒子…
6
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们知道 个球，平均分到两个盒子中，总共有 种分法。接下来，我们可以求出每种分法中，两个盒子中球的颜色数相同的情况数。最后，将两者相除即可。 我们可以预处理出组合数 ，然后使用记忆化搜索求解。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
桌面上有 2n 个颜色不完全相同的球，球的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。
所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。
注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例的解释部分）。
请返回「两个盒子中球的颜色数相同」的情况的概率。答案与真实值误差在 10-5 以内，则被视为正确答案
示例 1：
输入：balls = [1,1] 输出：1.00000 解释：球平均分配的方式只有两种： - 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子 - 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子 这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。
示例 2：
输入：balls = [2,1,1] 输出：0.66667 解释：球的列表为 [1, 1, 2, 3] 随机打乱，得到 12 种等概率的不同打乱方案，每种方案概率为 1/12 ： [1,1 / 2,3], [1,1 / 3,2], [1,2 / 1,3], [1,2 / 3,1], [1,3 / 1,2], [1,3 / 2,1], [2,1 / 1,3], [2,1 / 3,1], [2,3 / 1,1], [3,1 / 1,2], [3,1 / 2,1], [3,2 / 1,1] 然后，我们将前两个球放入第一个盒子，后两个球放入第二个盒子。 这 12 种可能的随机打乱方式中的 8 种满足「两个盒子中球的颜色数相同」。 概率 = 8/12 = 0.66667
示例 3：
输入：balls = [1,2,1,2] 输出：0.60000 解释：球的列表为 [1, 2, 2, 3, 4, 4]。要想显示所有 180 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 108 种情况是比较容易的。 概率 = 108 / 180 = 0.6 。
提示：
1 <= balls.length <= 81 <= balls[i] <= 6sum(balls)是偶数
解题思路
方法一：记忆化搜索 + 组合数学
我们知道 个球，平均分到两个盒子中，总共有 种分法。接下来，我们可以求出每种分法中，两个盒子中球的颜色数相同的情况数。最后，将两者相除即可。
我们可以预处理出组合数 ，然后使用记忆化搜索求解。
设计一个函数 ，表示当前从第 种球开始，第一个盒子剩余可放置 个球，两个盒子中球的颜色数的差为 的方案数。
函数 的执行逻辑如下：
- 如果 ，表示所有球都已经放完，如果 且 ，表示两个盒子中球的颜色数相同，返回 ，否则返回 ；
- 如果 ，表示第一个盒子中球的数量超过了 ，返回 ；
- 如果 不为 ，表示已经计算过，直接返回 ；
- 否则，枚举第 种球放入第一个盒子中的数量 ，则第 种球放入第二个盒子中的数量为 ，两个盒子中球的颜色数的变化量为 。如果所有球都放入第一个盒子中，那么 ；如果所有球都放入第二个盒子中，那么 ；否则 。然后，递归计算 ，并将结果与 相乘，累加到答案中。最后，将答案存入 中，并返回答案。
时间复杂度 ，空间复杂度 。其中 和 分别是球的总数和颜色的种数。
class Solution:
def getProbability(self, balls: List[int]) -> float:
@cache
def dfs(i: int, j: int, diff: int) -> float:
if i >= k:
return 1 if j == 0 and diff == 0 else 0
if j < 0:
return 0
ans = 0
for x in range(balls[i] + 1):
y = 1 if x == balls[i] else (-1 if x == 0 else 0)
ans += dfs(i + 1, j - x, diff + y) * comb(balls[i], x)
return ans
n = sum(balls) >> 1
k = len(balls)
return dfs(0, n, 0) / comb(n << 1, n)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | and space complexity depend on the number of colors k and maximum balls per color. Using DP reduces exponential exploration but requires O(k * n * n) states in the worst case, where n is half the total number of balls. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Expect state transition dynamic programming recognition and careful combinatorial reasoning.
- question_mark
Watch for factorial handling of identical balls to avoid overcounting or undercounting.
- question_mark
Clarify distinction between boxes early to prevent incorrect probability assumptions.
常见陷阱
外企场景- error
Confusing box identity and treating distributions as identical when boxes are distinct.
- error
Forgetting to include all possible ways to split balls of a single color between boxes.
- error
Ignoring memoization, leading to exponential runtime for even small input sizes.
进阶变体
外企场景- arrow_right_alt
Compute probability with more than two boxes while maintaining distinct color equality constraints.
- arrow_right_alt
Calculate probability when some balls are fixed in specific boxes initially, modifying DP states.
- arrow_right_alt
Find expected number of distinct colors in each box instead of probability equality.