1331. array sequence number conversion - quick sort plus binary search

1331. Array number conversion - Quick sort plus binary search

Give you an array of integers arr , Please replace each element in the array with their ordinal number after sorting .

The serial number represents how big an element is . The rules for serial numbers are as follows ：

 The serial number from  1  Numbered starting .
 The bigger an element is , So the bigger the serial number . If two elements are equal , So they have the same serial number .
 The serial number of each number should be as small as possible .

Example 1：

Input ：arr = [40,10,20,30]
Output ：[4,1,2,3]
explain ：40 It's the biggest element . 10 It's the smallest element . 20 It's the second smallest number . 30 It's the third smallest number .

Example 2：

Input ：arr = [100,100,100]
Output ：[1,1,1]
explain ： All elements have the same sequence number .

Example 3：

Input ：arr = [37,12,28,9,100,56,80,5,12]
Output ：[5,3,4,2,8,6,7,1,3]
The solution code is as follows ：

/** * Note: The returned array must be malloced, assume caller calls free(). */
void quick(int *a,int low,int high){
    
    int l=low,h=high;
    if(low<high){
    
        int 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 find_index(int *a,int low ,int high,int val){
    
    // printf("%d %d ",low,high);
    if(low==high){
    
        return low;
    }
    if(low<high){
    
        int mid=(low+high)/2;
        if(a[mid]>val){
    
            return find_index(a,low,mid-1,val);
        }
         if(a[mid]<val){
    
            return find_index(a,mid+1,high,val);
        }
        return mid;
        

    }
    return low;
}

int* arrayRankTransform(int* arr, int arrSize, int* returnSize){
    
    int *a=(int *)malloc(sizeof(int)*arrSize);
    int *r=(int *)malloc(sizeof(int)*arrSize);
    * returnSize=arrSize;
    if(arrSize==0) return arr;
    int i;
    for(i=0;i<arrSize;i++){
    
       a[i]=arr[i];
    }
    quick(a,0,arrSize-1);
    r[0]=1;
    for(i=1;i<arrSize;i++){
    
    // printf("%d ",a[i]);
      if(a[i]>a[i-1]){
    
          r[i]=r[i-1]+1;

      }
      else{
    
          r[i]=r[i-1];
      }
    }
     for(i=0;i<arrSize;i++){
    
       int index= find_index(a,0,arrSize-1,arr[i]);
       arr[i]=r[index];
    }
return arr;

   


}