原文链接: https://leetcode-cn.com/problems/qi-wang-ge-shu-tong-ji

英文原文

中文题目

某互联网公司一年一度的春招开始了，一共有 n 名面试者入选。每名面试者都会提交一份简历，公司会根据提供的简历资料产生一个预估的能力值，数值越大代表越有可能通过面试。

小 A 和小 B 负责审核面试者，他们均有所有面试者的简历，并且将各自根据面试者能力值从大到小的顺序浏览。由于简历事先被打乱过，能力值相同的简历的出现顺序是从它们的全排列中等可能地取一个。现在给定 n 名面试者的能力值 scores，设 X 代表小 A 和小 B 的浏览顺序中出现在同一位置的简历数，求 X 的期望。

提示：离散的非负随机变量的期望计算公式为 。在本题中，由于 X 的取值为 0 到 n 之间，期望计算公式可以是 。

示例 1：

输入：scores = [1,2,3]

输出：3

解释：由于面试者能力值互不相同，小 A 和小 B 的浏览顺序一定是相同的。X的期望是 3 。

示例 2：

输入：scores = [1,1]

输出：1

解释：设两位面试者的编号为 0, 1。由于他们的能力值都是 1，小 A 和小 B 的浏览顺序都为从全排列 [[0,1],[1,0]] 中等可能地取一个。如果小 A 和小 B 的浏览顺序都是 [0,1] 或者 [1,0] ，那么出现在同一位置的简历数为 2 ，否则是 0 。所以 X 的期望是 (2+0+2+0) * 1/4 = 1

示例 3：

输入：scores = [1,1,2]

输出：2

限制：

• 1 <= scores.length <= 10^5
• 0 <= scores[i] <= 10^6

通过代码

高赞题解

本篇题解是写给像我一样的概统小白的orz，大佬请自行忽略
1.对于能力值不重复（即能力值出现次数为1）的员工，排序后在A和B的审阅顺序中一定相同，期望为1。
2.对于能力值重复（即能力值出现次数>1）的员工，假设总共有N个拥有重复能力值的员工，那么期望计算为所有可能的能力值之和/总共的可能数，其中分母为N!*N!，即A和B都遍取所有可能。
分子的计算是重点：

先来看一种更特殊的情况，假设N=4，取A的审阅顺序为0 1 2 3，则B有4!=24种可能，这里不全部列出来，只需要关注我们关注的部分，即这所有可能中有多少个“相同位”（在这个特殊例子，指第1位为0或第2位为1或第3位为2或第4位为3）：

0 1 2 3
0 1 3 2
0 2 1 3
0 2 3 1
0 3 1 2
0 3 2 1

很容易看出来，第一列的0共提供了(4-1)!=3!=6个“相同位”，同理，1、2、3也都提供了(4-1)!个“相同位”，即有4个4(4-1)!=4!。
上面只是取了A审阅顺序为0 1 2 3这种情况，那么很容易知道A审阅顺序总共有4!种可能。
这些“相同位”就构成了我们上文中提到的分子——“所有可能的能力值之和”，根据上面讨论的结论，有4!*4!，其中第一个4!为A可能的审阅顺序数，第二个4!为A审阅顺序确定后“相同位”的个数。

3.综上，对于能力值不重复的员工，期望为1，能力值重复的员工，所有能力值相同的员工（可以有多组能力值相同的员工）期望总和为1，所以，问题转化为求原始数据中有多少个不重复的数。

class Solution {
public:
    int expectNumber(vector<int>& scores) {
        //C++STL，实际上就是计算总共有多少个不同的元素，好处是不用排序（因为原数据是无序的），时间复杂度O(nlogn)，空间复杂度O(n)
        unordered_set<int> s;
        for(int i:scores)s.insert(i);
        return s.size();
    }
};

另外，非常感谢@wx2700317大佬的详细讲解，我才能总结出这套证明过程，非常感谢！^_^

统计信息

通过次数	提交次数	AC比率
7164	10359	69.2%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言