最近签到打卡，每日额外再刷两道题攒积分。遇到一个简单题LCP 11. 期望个数统计，挺有意思的，记录一下分析过程并重温概率学知识。
题目
给定n个数的数组scores，小 A 和小 B 负责对scores按从高到低选择元素，对于其中相同的元素会等概率选择。求 A 和 B选择的顺序中相同次序是同一元素的总个数的期望。
分析
首先很容易将数组划分为不同段，只出现一次的元素选择是完全一致的，只有出现至少2次的元素需要重新计算期望。不同段之间是独立的（从高到低选择），那么针对每一段重复k个元素来研究其期望，最终结果是各段期望之和。
子问题：长度为m的数组，A 和 B随机选择m次，求选择的排列中同一位置是同一元素的总个数的期望。
原问题这里每个元素值一样，但实际是考虑在原位置上是同一元素，则可以看作是不同值更方便。
进一步，可以固定其中一个人选择次序，求另一个人 m! 中情况中元素出现相同位置个数的期望。
很容易写出 k 位置个不相同时的答案（写错了！！！使k个位置互不相同的排列数并不是\({C_{m}^{k} (k!-1)}\)）：
【【【【分析错了 忽略该部分】】】】
概率为
期望为
\[\frac {C_{m}^{k} (k!-1)}{m!}(m-k) \]整理得
\[\frac {C_{m}^{k} (k!-1)}{m!}(m-k)=\frac{(k!-1)(m-k)}{k!(m-k)!}=\frac{(k!-1)}{k!(m-k-1)!}=\frac{(1-1/k!)}{(m-k-1)!} \]子问题答案
\[\sum_{k=2}^{m-2}=\frac{(1-1/k!)}{(m-k-1)!} + \frac 1 {m!}(注:k=0) \]然后就不会化简了。
【【【【分析错了 忽略该部分】】】】
找规律
题目给定当 k=2 时结果为 1。 分析当 k = 3时的情况，看能否找出规律。
假设数组为 [1, 2, 3]，B的选择会有 3!=6种，分别是
| 排列 | 相同元素个数 | 概率 |
|---|---|---|
| [1, 2, 3] | 3=(1+1+1) | 1/6 |
| [1, 3, 2] | 1 | 1/6 |
| [2, 1, 3] | 1 | 1/6 |
| [2, 3, 1] | 0 | 1/6 |
| [3, 1, 2] | 0 | 1/6 |
| [3, 2, 1] | 1 | 1/6 |
结果：\(3*1/6+1*1/6+1*1/6+1*1/6=1\)
大胆猜测结果恒为一，直接提交代码：return len(set(scores))，AC！
期望计算
对于上表，如果对于 m 个数，依旧按 m! 种情况列出来统计求和，这将很难计算相同元素个数。当合并观察每个元素在原有位置上出现的总次数时，一切清晰了起来。
例如，1出现在第一位共 2次，2出现在第二位共 2 次，3出现在第三位共 2 次，每次的概率均为 1/6。
对于一般情况，m 个数，每个数出现在原有位置共 (m-1)! 次，总期望为
\[\sum^m\frac 1{m!} {(m-1)!} = \frac {m*(m-1)!}{m!} = 1 \]（完）
标签：11,期望,相同,LCP,元素,个数,选择,frac,Leetcode From： https://www.cnblogs.com/izcat/p/16795540.html