leetcode
leetcode 2851 ~ 2900
期望个数统计

期望个数统计

难度:

标签:

题目描述

English description is not available for the problem. Please switch to Chinese.

代码结果

运行时间: 42 ms, 内存: 31.8 MB


// 思路:由于能力值相同的简历的出现顺序是从它们的全排列中等可能地取一个,因此,对于每一个位置i,简历出现在同一位置的概率是1/n。因此,期望X = n * (1/n) = 1。
// 直接返回1即可。

import java.util.stream.*;

public class Solution {
    public double expectedValue(int[] scores) {
        int n = scores.length;
        return 1.0;
    }
}

解释

方法:

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

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
题解中提到,当两个面试者的能力值相同,他们在小A和小B的浏览顺序中的相对位置存在随机性。请问是如何计算这种情况对X的期望值贡献的?
在考虑相同能力值的情况下,对于每一种能力值,假设有 k 个面试者拥有这个能力值。小A和小B查看这 k 个简历时的顺序都是从这些简历的全排列中等可能地取一个。因此,对于每一个位置 i,小A和小B看到同一个简历的概率是 1/k。因此,对于每一组相同能力值的简历,其对 X 的贡献是 1。综上,不同能力值的组数即为 X 的期望值。
🦆
题解中使用集合来去除重复的能力值,这种方法是否考虑了能力值相同的简历数量对期望值X的潜在影响?
题解中使用集合去除重复元素的方法简化了问题,没有直接考虑相同能力值的简历数量对 X 的影响。这是因为对于每一组相同的能力值,无论这个组中有多少简历,它们对期望值 X 的贡献总是 1。因此,只需计算不同能力值的组数即可,而不需要关注每组中具体的简历数量。
🦆
题解返回的是不同能力值的数量,为什么这个数量可以直接用作期望值X的计算结果?
对于每一种不同的能力值,它们在小A和小B的浏览顺序中是确定的,且位置相同。因此,每一种不同的能力值直接对应于小A和小B浏览顺序中处于相同位置的简历数。由于每组相同能力值的简历对 X 的贡献为 1,不同能力值的总数正好等于 X 的期望值。

相关问题