题目描述

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

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

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

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

样例

输入：balls = [1,1]
输出：1.00000
解释：球平均分配的方式只有两种：
- 颜色为 1 的球放入第一个盒子，颜色为 2 的球放入第二个盒子
- 颜色为 2 的球放入第一个盒子，颜色为 1 的球放入第二个盒子
这两种分配，两个盒子中球的颜色数都相同。所以概率为 2/2 = 1 。

输入：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

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

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

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

提示：

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

算法分析

题目意思：给定2n个球，有k种颜色，每种颜色有balls[i]个球，随机打乱，前n个和后n个分开放在不同的两个盒子，问两个盒子中颜色数量相同（n个球x种颜色）的求占总情况的概率是多少？

可重复全排列的方案数 $\frac{S!}{a_1! a_2! … a_k!}$,其中$S = a_1 + a_2 + … + a_k$

• 总方案数down：用上面的公式算出总方案数，S是总球数，$a_i$是i号颜色的球数

• 合法的方案数up：由于左边的盒子每种颜色选定的球固定时，右边盒子中各颜色的球也随之固定，通过dfs枚举出左边盒子中(left[]数组)k种颜色的球各选多少个，

  • 且当选出的个数是恰好是n个时，算出左边盒子的颜色个数和右边盒子的颜色个数
  • 且当两个盒子的颜色个数相同时，可以通过上面的公式算出左边盒子的方案数x和右边盒子的方案数y，更新up = up + x * y

• 结果:up / down

时间复杂度

Java 代码

class Solution {
    static int N = 10;
    static double[] fac = new double[50];
    static int[] balls;
    static int n,sum;
    static int[] left = new int[N];
    static int[] right = new int[N];
    static double up,down;// up表示满足要求的方案数，down表示总方案数
    static void init()
    {
        fac[0] = 1;
        for(int i = 1;i < 50;i ++) fac[i] = fac[i - 1] * i;
    }
    static double get(int[] s)
    {
        int sum = 0;
        for(int i = 0;i < n;i ++) sum += s[i];

        double res = fac[sum];
        for(int i = 0;i < n;i ++) res /= fac[s[i]];

        return res;
    }
    static void dfs(int u,int cnt)
    {
        if(u == n)
        {
            //若枚举到当前的球数是总的一半
            if(cnt == sum / 2)
            {
                //算出左边的颜色个数和右边的颜色个数
                int l = 0,r = 0;
                for(int i = 0;i < n;i ++)
                {
                    if(left[i] != 0) l ++;
                    if(right[i] != 0) r++;
                }
                if(l == r) up += get(left) * get(right);
            }
            return ;
        }
        //当前颜色的球选多少个
        for(int i = 0;i <= balls[u];i ++)
        {
            left[u] = i;
            right[u] = balls[u] - i;
            dfs(u + 1,cnt + i);
        }
    }
    public double getProbability(int[] balls) {
        n = balls.length;
        this.balls = balls;
        up = 0;
        down = 0;

        Arrays.fill(left,0);
        Arrays.fill(right,0);
        //算出总球数
        sum = 0;
        for(int i = 0;i < balls.length;i ++) sum += balls[i];
        //预处理阶乘
        init();

        dfs(0,0);

        down = get(balls);
        return up / down;
    }
}