原文链接: https://leetcode-cn.com/problems/probability-of-a-two-boxes-having-the-same-number-of-distinct-balls

英文原文

Given 2n balls of k distinct colors. You will be given an integer array balls of size k where balls[i] is the number of balls of color i.

All the balls will be shuffled uniformly at random, then we will distribute the first n balls to the first box and the remaining n balls to the other box (Please read the explanation of the second example carefully).

Please note that the two boxes are considered different. For example, if we have two balls of colors a and b, and two boxes [] and (), then the distribution [a] (b) is considered different than the distribution [b] (a) (Please read the explanation of the first example carefully).

Return the probability that the two boxes have the same number of distinct balls. Answers within 10-5 of the actual value will be accepted as correct.

 

Example 1:

Input: balls = [1,1]
Output: 1.00000
Explanation: Only 2 ways to divide the balls equally:
- A ball of color 1 to box 1 and a ball of color 2 to box 2
- A ball of color 2 to box 1 and a ball of color 1 to box 2
In both ways, the number of distinct colors in each box is equal. The probability is 2/2 = 1

Example 2:

Input: balls = [2,1,1]
Output: 0.66667
Explanation: We have the set of balls [1, 1, 2, 3]
This set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equal probability (i.e. 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]
After that, we add the first two balls to the first box and the second two balls to the second box.
We can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.
Probability is 8/12 = 0.66667

Example 3:

Input: balls = [1,2,1,2]
Output: 0.60000
Explanation: The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.
Probability = 108 / 180 = 0.6

Example 4:

Input: balls = [3,2,1]
Output: 0.30000
Explanation: The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.
Probability = 18 / 60 = 0.3

Example 5:

Input: balls = [6,6,6,6,6,6]
Output: 0.90327

 

Constraints:

• 1 <= balls.length <= 8
• 1 <= balls[i] <= 6
• sum(balls) is even.

中文题目

桌面上有 2n 个颜色不完全相同的球，球上的颜色共有 k 种。给你一个大小为 k 的整数数组 balls ，其中 balls[i] 是颜色为 i 的球的数量。

所有的球都已经 随机打乱顺序 ，前 n 个球放入第一个盒子，后 n 个球放入另一个盒子（请认真阅读示例 2 的解释部分）。

注意：这两个盒子是不同的。例如，两个球颜色分别为 a 和 b，盒子分别为 [] 和 ()，那么 [a] (b) 和 [b] (a) 这两种分配方式是不同的（请认真阅读示例 1 的解释部分）。

请计算「两个盒子中球的颜色数相同」的情况的概率。

 

示例 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 。

示例 4：

输入：balls = [3,2,1]
输出：0.30000
解释：球的列表为 [1, 1, 1, 2, 2, 3]。要想显示所有 60 种随机打乱方案是很难的，但只检查「两个盒子中球的颜色数相同」的 18 种情况是比较容易的。
概率 = 18 / 60 = 0.3 。

示例 5：

输入：balls = [6,6,6,6,6,6]
输出：0.90327

 

提示：

• 1 <= balls.length <= 8
• 1 <= balls[i] <= 6
• sum(balls) 是偶数
• 答案与真实值误差在 10^-5 以内，则被视为正确答案

通过代码

高赞题解

题目翻译应该背锅。
正确的理解是，2n个球，随机挑选n个，那么这n个中所有的颜色数量等于另外n个中所有的颜色数量的概率。即如果一个箱子里有三种不同的颜色比如红黄蓝，那另外一个箱子里也必须有三种不同的颜色，比如绿红蓝。
第一想法就是组合数。上网查询找回高中组合数学知识：


好的我们现在知道最多48个球的时候，一共有C(48, 24)种挑选方法,拿python算了一下大概是10^13数量级，似乎也不多，然后我们要在这么多挑选方法中找到那些左边右边颜色数量相同的。
方法就是dfs，一层一层找，举例来说：（3，2，1）
第一层是3个颜色为0的球。
我们遍历它，可以找到4种放法，即放0个到第一个箱子，放3个到第二个箱子，或者放1个到第一个箱子，放2个到第二个箱子，或者放2个到第一个箱子，放1个到第二个箱子，或者最后，放3个到第一个箱子，放2个到第二个箱子。
一共就这四种情况，我们分别算出在这四种情况下满足条件的概率，再乘以这四种情况的权重（即这四种情况分别出现的概率）即可。
假设我们的深搜函数是 dfs(balls, m, greatersum, greatercolor)
balls是不同的球有多少个，m是当前搜索的位置（第几种颜色的球），greatersum是左边的箱子比右边的箱子多出多少个球，而greatercolor是左边的箱子比右边多出多少种颜色。
我们只有在后两个参数都为0的时候，才可以说是一种满足我们条件的情况。
那么，在第一层，我们要返回的概率就是：
( combination(3, 0)/powerof2[3] )*dfs(balls, 2, -3, -1)
+( combination(3, 1)/powerof2[3] )*dfs(balls, 2, -1, 0)
+( combination(3, 2)/powerof2[3] )*dfs(balls, 2, 1, 0)
+( combination(3, 3)/powerof2[3] )*dfs(balls, 2, 3, 0)
前面一部分代表着在所有选择方法中，选择出0/1/2/3个颜色为0的球放在左边的箱子（同时会有3/2/1/0个颜色为0的球放在右边的箱子）的概率，后面一部分代表在这种前提下，能够满足我们要求（最终两边球的个数相等以及球的颜色数相等）的概率。加起来返回就是 在所有的选择情况下，左右箱子个数相同且颜色数相同的概率，注意，这里的所有情况包括了左边箱子有全部的球，右边的箱子一个都没有这种情况，我们再将这个概率除以两边放的球数量相同的概率（即如果一共有2n个球，就要除以C(2n, n)/2^(2n)），就是题目要我们求的结果。
上代码：

class Solution {
public:
    int left[10]; //剩余的球的数量，用于剪枝
    double powerof2[15] = {1, 2, 4, 8, 16,32, 64, 128, 256,512,1024,2048,4096,8192,16384}; //2的幂，用来算所有组合情况
    int n = 0;
    long long factorial[15];//算阶乘，用于计算组合数
    double getProbability(vector<int>& balls) {
        calculatefactorial();
        n = balls.size();
        int sum = 0; //一共有多少个球，用于最后的除法
        for(int i = 0; i < n; i++)
            sum += balls[i];
        double q = 1; //计算出C(2n, n)/2^(2n)，即满足左n右n的概率
        for(int i = 1; i <= sum/2; i++){
            q *= (i+sum/2)*1.0/i/4;
        }
        left[n-1] = balls[n-1]; //计算剩余球数，用于剪枝
        for(int i = n-2; i >= 0; i--)
            left[i] = left[i+1] + balls[i];
        return dfs(balls, 0, 0, 0)/q;
    }
    //计算阶乘，不解释
    void calculatefactorial(){
        factorial[0] = 1;
        for(int i = 1; i <= 10; i++)
            factorial[i] = i * factorial[i-1];
    }
    //根据公式算组合数
    int combination(int a, int b){
        return factorial[a]/(factorial[b]*factorial[a-b]);
    }
    //深搜函数，balls是题目给的数组，m代表当前搜索颜色m，greatersum是左边的箱子比右边箱子多几个球，greatercolor是左边比右边多几种颜色
    double dfs(vector<int> & balls, int m, int greatersum, int greatercolor){
        if(m == n) //只有左边右边球的数量和颜色种类的数量相等时才算，否则免谈
            return greatersum == 0 && greatercolor == 0;
        //剪枝，假设目前还剩余x个球没有分配，但是左边比右边的球多的数量，或者右边箱子比左边箱子多出的球的数量大于x，那么我们无论怎么分配，都不可能在最后满足左右球的数量相等这个条件，所以剪枝
        if(abs(greatersum) > left[m])
            return 0;
        double result = 0;
        //计算取不同数量的球放在左边，最后满足条件的概率 （感谢来自 @金木盐 的改进）
        for(int i = 0; i <= balls[m];i ++){
            int color = i == 0 ? -1 : (i == balls[m] ? 1 : 0);
            result += (combination(balls[m], i) / powerof2[balls[m]]) * 
                dfs(balls, m + 1, greatersum + i - (balls[m] - i), greatercolor + color);
        }
        /* 原来的写法需要写三次，太不简洁了
        for(int i = 0; i <= balls[m];i ++){
            if(i == 0){
                result +=  dfs(balls, m+1, greatersum-balls[m], greatercolor-1)/powerof2[balls[m]];
            }
            else if(i == balls[m]){
                result +=  dfs(balls, m+1, greatersum+balls[m], greatercolor+1)/powerof2[balls[m]];
            }
            else{
                result += (combination(balls[m], i)/powerof2[balls[m]]) * dfs(balls, m+1, greatersum + (i-(balls[m]-i)), greatercolor);
            }
        }
        */
        return result;
    }

};

统计信息

通过次数	提交次数	AC比率
1707	2757	61.9%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言