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() 需要分开声明
No comments:
Post a Comment