Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1331.html
1331. Rank Transform of an Array (Easy)
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
Related Topics:
Array
Solution 1.
-
class Solution { public int[] arrayRankTransform(int[] arr) { Set<Integer> set = new HashSet<Integer>(); for (int num : arr) set.add(num); List<Integer> list = new ArrayList<Integer>(); for (int num : set) list.add(num); Collections.sort(list); Map<Integer, Integer> numRankMap = new HashMap<Integer, Integer>(); int size = list.size(); for (int i = 0; i < size; i++) { int num = list.get(i); numRankMap.put(num, i + 1); } int length = arr.length; int[] ranks = new int[length]; for (int i = 0; i < length; i++) { int num = arr[i]; int rank = numRankMap.get(num); ranks[i] = rank; } return ranks; } } ############ class Solution { public int[] arrayRankTransform(int[] arr) { Set<Integer> s = new HashSet<>(); for (int v : arr) { s.add(v); } List<Integer> alls = new ArrayList<>(s); alls.sort((a, b) -> a - b); Map<Integer, Integer> m = new HashMap<>(); for (int i = 0; i < alls.size(); ++i) { m.put(alls.get(i), i + 1); } int[] ans = new int[arr.length]; for (int i = 0; i < arr.length; ++i) { ans[i] = m.get(arr[i]); } return ans; } }
-
// OJ: https://leetcode.com/problems/rank-transform-of-an-array/ // Time: O(NlogN) // Space: O(N) class Solution { public: vector<int> arrayRankTransform(vector<int>& arr) { set<int> s(arr.begin(), arr.end()); unordered_map<int, int> m; vector<int> ans(arr.size(), 0); int i = 0; for (auto it = s.begin(); it != s.end(); ++it) m[*it] = ++i; for (int j = 0; j < arr.size(); ++j) ans[j] = m[arr[j]]; return ans; } };
-
class Solution: def arrayRankTransform(self, arr: List[int]) -> List[int]: m = {v: i for i, v in enumerate(sorted(set(arr)), 1)} return [m[v] for v in arr]
-
func arrayRankTransform(arr []int) []int { s := make(map[int]bool) for _, v := range arr { s[v] = true } var alls []int for v := range s { alls = append(alls, v) } sort.Ints(alls) m := make(map[int]int) for i, v := range alls { m[v] = i + 1 } var ans []int for _, v := range arr { ans = append(ans, m[v]) } return ans }
-
function arrayRankTransform(arr: number[]): number[] { const t = [...arr].sort((a, b) => a - b); let m = 0; for (let i = 0; i < t.length; ++i) { if (i === 0 || t[i] !== t[i - 1]) { t[m++] = t[i]; } } const search = (t: number[], right: number, x: number) => { let left = 0; while (left < right) { const mid = (left + right) >> 1; if (t[mid] > x) { right = mid; } else { left = mid + 1; } } return left; }; const ans: number[] = []; for (const x of arr) { ans.push(search(t, m, x)); } return ans; }