### 題目

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

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

提示：離散的非負(fù)隨機變量的期望計算公式為 。在本題中，由于 X 的取值為 0 到 n 之間，期望計算公式可以是 。

示例 1：

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

輸出：3

解釋：由于面試者能力值互不相同，小 A 和小 B 的瀏覽順序一定是相同的。X的期望是 3 。

示例 2：

輸入：scores = [1,1]

輸出：1

解釋：設(shè)兩位面試者的編號為 0, 1。由于他們的能力值都是 1，小 A 和小 B 的瀏覽順序都為從全排列 [[0,1],[1,0]] 中等可能地取一個。如果小 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

###?解題思路

題目的意思簡化為對給定數(shù)組中，有多少的不重復(fù)的數(shù)的個數(shù)

對于測試樣例，如果用暴力求解，即O（n^2）的時間復(fù)雜度，會超時（不同平臺測試樣例不同，具體問題具體分析）

所以為了找到比這個還要小的時間復(fù)雜度，所以可以考慮的算法即為快排，然后再除重計數(shù)。

###?代碼

void?QuickSort(int*?scores,int?low,int?high)

{

????if(low<high)

????{

????????int?pivotpos=Partition(scores,low,high);

????????QuickSort(scores,low,pivotpos-1);

????????QuickSort(scores,pivotpos+1,high);

????}?

}

int?Partition(int*?scores,int?low,int?high)

{

????int?pivot=scores[low];

????while(low<high)

????{

????????while(low<high&&scores[high]>=pivot)

????????????--high;

????????scores[low]=scores[high];

????????while(low<high&&scores[low]<=pivot)

????????????++low;

????????scores[high]=scores[low];

????}

????scores[low]=pivot;

????return?low;

}

int?expectNumber(int*?scores,?int?scoresSize){

????int?i,j;

????int?count=1;

????QuickSort(scores,0,scoresSize-1);

????for(i=0;i<scoresSize-1;i++)

????{

????????if(scores[i]!=scores[i+1])

????????{

????????????count++;

????????}

????????

????}

????return?count;

}