Leetcode 1331. array sequence number conversion

【LetMeFly】1331. Array number conversion

Force button topic link ：https://leetcode.cn/problems/rank-transform-of-an-array/

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

Method 1 ：sort + Hashtable

First, copy a copy of the original array into the temporary array , And sort the temporary array

After ordering , Traverse the temporary array , Record your ranking （ Use a variable last To store the last value , If this value is different from the previous one, it will rank +1） To hash table

Traverse the original array , Modify the value “ Map from the hash table to the value after ranking ”

• Time complexity $O(n\log n)$, among $n$ Is the number of elements in the array . Sorting time $n\log n$
• Spatial complexity $O(N\log N)$. Hashtable 、 Sorting and temporary arrays consume space $O(n)$

AC Code

C++

class Solution {
    
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
    
        vector<int> toSort = arr;
        sort(toSort.begin(), toSort.end());
        unordered_map<int, int> ma;
        int th = 0;
        int last = -1e9 - 1;
        for (int i = 0; i < toSort.size(); i++) {
    
            if (toSort[i] == last)
                continue;
            ma[toSort[i]] = ++th;
            last = toSort[i];
        }
        for (int& t : arr) {
    
            t = ma[t];
        }
        return arr;
    }
};

Python

Grammar sugar is so simple

Python Code Copy From Try to answer the official questions

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        ranks = {
    v: i for i, v in enumerate(sorted(set(arr)), 1)}
        return [ranks[v] for v in arr]

Synchronous posting on CSDN, Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/126030218