1331. Rank Transform of an Array (easy)

Q:

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

• Rank is an integer starting from 1.
• The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
• Rank should be 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. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

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

Constraints:

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

A:

搞一个priority_queue, 复杂类型，然后从小到大取就行了。

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        struct A
        { 
            int val, index;
            A(int v, int i):val(v), index(i){};
        };
        struct compareA
        {
            bool operator()(A const& p1, A const& p2)
            {
                if(p1.val == p2.val)
                {
                    return p1.index > p2.index;
                }
                return p1.val > p2.val;
            }
        };
        vector<int> res(arr.size());
        priority_queue<A, vector<A>, compareA> Q;
        for(int i =0; i<arr.size(); ++i)
        {
            Q.push(A(arr[i],i));
        }
        int curRank = 0, preVal = 0;
        while(!Q.empty())
        {
            A p = Q.top();
            Q.pop();
            if(curRank == 0 || preVal != p.val)
            {
                curRank++;
                preVal = p.val;
            }
            res[p.index] = curRank;
        }        
        return res;
    }
};

another way is to copy arr, and sort it, then remove duplicate, then map their index as rank.


Learned：
1:  priority_queue,  默认的，p1 < p2, 会导致max queue.  如果用min queue, 需要 >
2:  how to create Struct, and apply the Compare operator(),
3: Q.top(),   Q.pop() 需要分开声明