Description#
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
Solutions#
Solution 1#
1
2
3
4
| class Solution:
def arrayRankTransform(self, arr: List[int]) -> List[int]:
t = sorted(set(arr))
return [bisect_right(t, x) for x in arr]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public int[] arrayRankTransform(int[] arr) {
int n = arr.length;
int[] t = arr.clone();
Arrays.sort(t);
int m = 0;
for (int i = 0; i < n; ++i) {
if (i == 0 || t[i] != t[i - 1]) {
t[m++] = t[i];
}
}
int[] ans = new int[n];
for (int i = 0; i < n; ++i) {
ans[i] = Arrays.binarySearch(t, 0, m, arr[i]) + 1;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> t = arr;
sort(t.begin(), t.end());
t.erase(unique(t.begin(), t.end()), t.end());
vector<int> ans;
for (int x : arr) {
ans.push_back(upper_bound(t.begin(), t.end(), x) - t.begin());
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func arrayRankTransform(arr []int) (ans []int) {
t := make([]int, len(arr))
copy(t, arr)
sort.Ints(t)
m := 0
for i, x := range t {
if i == 0 || x != t[i-1] {
t[m] = x
m++
}
}
t = t[:m]
for _, x := range arr {
ans = append(ans, sort.SearchInts(t, x)+1)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| 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;
}
|
