期望个数统计

难度: Easy

某互联网公司一年一度的春招开始了，一共有 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

Submission

运行时间: 42 ms

内存: 31.8 MB

class Solution:
    def expectNumber(self, scores: List[int]) -> int:

        return len(set(scores))

Explain

题解的核心思路是利用集合来消除数组中的重复元素。由于小A和小B的浏览顺序都是基于能力值从大到小，因此如果两个面试者的能力值相同，他们在小A和小B的浏览顺序中的相对位置存在随机性。但是，对于不同的能力值，小A和小B一定会在相同的位置看到这些简历。因此，只有不重复的能力值会贡献到期望的计算中。所以，问题转化为计算不同能力值的数量。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def expectNumber(self, scores: List[int]) -> int:
        # 使用集合去除scores中的重复元素
        unique_scores = set(scores)
        # 返回集合的大小，即不同能力值的数量
        return len(unique_scores)

Explore

在考虑相同能力值的情况下，对于每一种能力值，假设有 k 个面试者拥有这个能力值。小A和小B查看这 k 个简历时的顺序都是从这些简历的全排列中等可能地取一个。因此，对于每一个位置 i，小A和小B看到同一个简历的概率是 1/k。因此，对于每一组相同能力值的简历，其对 X 的贡献是 1。综上，不同能力值的组数即为 X 的期望值。

题解中使用集合去除重复元素的方法简化了问题，没有直接考虑相同能力值的简历数量对 X 的影响。这是因为对于每一组相同的能力值，无论这个组中有多少简历，它们对期望值 X 的贡献总是 1。因此，只需计算不同能力值的组数即可，而不需要关注每组中具体的简历数量。

对于每一种不同的能力值，它们在小A和小B的浏览顺序中是确定的，且位置相同。因此，每一种不同的能力值直接对应于小A和小B浏览顺序中处于相同位置的简历数。由于每组相同能力值的简历对 X 的贡献为 1，不同能力值的总数正好等于 X 的期望值。