[leetcode] 1331. Array sequence number conversion

subject

1331. Array number conversion

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]

Tips ：

• 0 <= arr.length <= 105
• -109 <= arr[i] <= 109

Ideas

• Sort the array , Take the sorted subscript as the position of the array
• When encountering repeated numbers, the number of bits will not increase

Code

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        indexMap = {
    }
        ret = []
        index = 1
        for n in sorted(arr):
            if n not in indexMap:
                indexMap[n] = index
                index += 1
        for n in arr:
            ret.append(indexMap[n])
        return ret

Complexity

• Time complexity ：$O(n\log n)$
• Spatial complexity ：$O(n)$