最近签到打卡,每日额外再刷两道题攒积分。遇到一个简单题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