• 欢迎光临~

Leetcode简单题背后的数学规律 | LCP 11. 期望个数统计

开发技术 开发技术 2022-10-16 次浏览

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

期望为

[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^mfrac 1{m!} {(m-1)!} = frac {m*(m-1)!}{m!} = 1 ]


(完)

程序员灯塔
转载请注明原文链接:Leetcode简单题背后的数学规律 | LCP 11. 期望个数统计
喜欢 (0)