这是今年微软的一道面试题考究的要点,仍然是我之前博文【面试中的概率问题-数学期望】中提到的数学期望的递归特性
给定一个数组arr[0..N-1],其中每个元素值均不相同讓你求最小值,一个非常典型的做法是这样的:
现在问你minVal = arr[i]的执行次数的期望是多少?
依旧使用数学期望中的递归特性来解决这个问题峩们令数组元素个数为n时,对应的数学期望为f(n)
那么f(n)可以进行如下分解:
如果最小值是arr[0],概率为1/n执行次数为1次
如果最小值是arr[1],概率为1/n執行次数为1次+f(1)
如果最小值是arr[i],概率为1/n执行次数为1次+f(i)