1. 題目

某互聯(lián)網(wǎng)公司一年一度的春招開始了，一共有 n 名面試者入選。
每名面試者都會(huì)提交一份簡歷，公司會(huì)根據(jù)提供的簡歷資料產(chǎn)生一個(gè)預(yù)估的能力值，數(shù)值越大代表越有可能通過面試。

小 A 和小 B 負(fù)責(zé)審核面試者，他們均有所有面試者的簡歷，并且將各自根據(jù)面試者能力值從大到小的順序?yàn)g覽。由于簡歷事先被打亂過，能力值相同的簡歷的出現(xiàn)順序是從它們的全排列中等可能地取一個(gè)。
現(xiàn)在給定 n 名面試者的能力值 scores，設(shè) X 代表小 A 和小 B 的瀏覽順序中出現(xiàn)在同一位置的簡歷數(shù)，求 X 的期望。

在本題中，由于 X 的取值為 0 到 n 之間，期望計(jì)算公式可以是

示例 1： 輸入：scores = [1,2,3] 輸出：3 解釋：由于面試者能力值互不相同，小 A 和小 B 的瀏覽順序一定是相同的。 X的期望是 3 。示例 2： 輸入：scores = [1,1] 輸出：1 解釋：設(shè)兩位面試者的編號(hào)為 0, 1。 由于他們的能力值都是 1，小 A 和小 B 的瀏覽順序都為從全排列 [[0,1],[1,0]] 中等可能地取一個(gè)。 如果小 A 和小 B 的瀏覽順序都是 [0,1] 或者 [1,0] ，那么出現(xiàn)在同一位置的簡歷數(shù)為 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/qi-wang-ge-shu-tong-ji
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

2. 解題

• 比賽的時(shí)候就做出來這一題，戰(zhàn)隊(duì)排名 551/1066，繼續(xù)加油。

---

整體是有序的，分?jǐn)?shù)相同的順序打亂了。
1個(gè)分?jǐn)?shù)只有1位的，肯定重合。

class Solution { public:int expectNumber(vector<int>& scores) {set<int> s;for(int sc : scores)s.insert(sc);return s.size();} };

528 ms 71.2 MB

總結(jié)

以上是生活随笔為你收集整理的LeetCode LCP 11. 期望个数统计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。