requirements

Given an integer array arr, replace each element in the array with its sorted ordinal number.

The ordinal number indicates how big an element is. The rules for numbering are as follows:

Serial number The number starts from 1. The larger the element, the larger the ordinal number. If two elements are equal, they have the same ordinal number. Each number should be numbered as small as possible. Example 1:

Input: arr = [40,10,20,30] output: [4,1,2,3] explanation: 40 is the largest element. 10 is the smallest element. Twenty is the second smallest number. Thirty is the third smallest number.Copy the code

Example 2:

Input: arr = [100,100,100] output: [1,1,1] explanation: all elements have the same ordinal number.Copy the code

Example 3:

Input: arr = 37,12,28,9,100,56,80,5,12 [] output:,3,4,2,8,6,7,1,3 [5]Copy the code

The core code

class Solution:
    def arrayRankTransform(self, arr: List[int]) - >List[int] :
        l = sorted(arr)
        dic,rank = {},0
        pre_num = None
        for i,num in enumerate(l):
            ifpre_num ! = num: rank +=1
                dic[num] = rank
                pre_num = num
        res = []
        for num in arr:
            res.append(dic[num])
        return res
Copy the code

We sort the array, then use a dictionary to save its serial number, and finally output it to the list, which is the answer. Time complexity: O (NlogN) Space complexity: O (N)