LCP 11. Statistics of expected number

LCP 11. The expected number of statistics

The annual spring move of an Internet company began , Altogether n Interviewers were selected . Every interviewer will submit a resume , The company will generate an estimated ability value based on the resume data provided , The higher the value, the more likely it is to pass the interview .

Small A And small B Responsible for reviewing interviewers , They have resumes of all interviewees , And they will browse according to the interviewer's ability value from large to small . Because the resume has been disrupted in advance , Resumes with the same ability value appear in the order of medium possibility from their full ranking . Now given n The ability value of an interviewer scores, set up X For little A And small B The number of resumes that appear in the same position in the browsing order , seek X The expectations of the .

Tips ： The expected calculation formula of discrete nonnegative random variables is 1. In the subject , because X The values for 0 To n Between , The expected calculation formula can be 2.

Example 1：

 Input ：scores = [1,2,3]

 Output ：3

 explain ： Because the ability values of interviewers are different from each other , Small  A  And small  B  The browsing order must be the same .X The expectation is  3 .

Example 2：

 Input ：scores = [1,1]

 Output ：1

 explain ： Set the number of two interviewers as  0, 1. Because their ability values are  1, Small  A  And small  B  The browsing order of is from full order  [[0,1],[1,0]]  Take one moderately possible . If small  A  And small  B  The browsing order is  [0,1]  perhaps  [1,0] , So the number of resumes in the same position is  2 , It is  0 . therefore  X  The expectation is  (2+0+2+0) * 1/4 = 1

Example 3：

 Input ：scores = [1,1,2]

 Output ：2

Limit ：

The solution code is as follows ：

void quick(int *a,int low,int high){
    
    if(low<high){
    
        int l=low,h=high,p=a[low];
        while(low<high){
    
            while(low<high&&a[high]>=p){
    
                high--;
            }
            a[low]=a[high];
            while(low<high&&a[low]<=p){
    
                low++;
            }
            a[high]=a[low];
        }
        a[low]=p;
        quick(a,l,low-1);
        quick(a,low+1,h);
    }
}

int expectNumber(int* scores, int scoresSize){
    
    int count=0;
  
  quick(scores,0,scoresSize-1);
    int base=scores[0];
    int i;
    // printf("%d ",scores[0]);
    for(i=1;i<scoresSize;i++){
    
       
        if(scores[i]!=base){
    
            count++;
            // printf("%d %d ",scores[i],count);
            base=scores[i];
        }

    }
    return count+1;

}