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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
// 1331. Rank Transform of an Array
#include "leetcode.h"
/*
* given an array of integers 'arr', replace each element with its rank. the
* rank reprsents 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.
*/
int cmp(const void *a, const void *b) {
int *x = (int *)a, *y = (int *)b;
return *x - *y;
}
int search(int *a, int size, int v) {
int l = 0, r = size;
while (l < r) {
int m = l + (r - l) / 2;
if (a[m] == v)
return m;
else if (a[m] > v)
r = m;
else
l = m;
}
return -1;
}
int *arrayRankTransform(int *arr, int arrSize, int *returnSize) {
*returnSize = arrSize;
int *ans = (int *)malloc(arrSize * sizeof(int));
if (!arrSize)
return ans;
int vals[arrSize], ranks[arrSize];
memcpy(vals, arr, sizeof(vals));
qsort(vals, arrSize, sizeof(int), cmp);
for (int i = 1; i < arrSize; i++)
ranks[i] = vals[i] == vals[i - 1] ? ranks[i - 1] : ranks[i - 1] + 1;
for (int i = 0; i < arrSize; i++) {
int j = search(vals, arrSize, arr[i]);
ans[i] = ranks[j];
}
return ans;
}
int main() {
int a1[] = {40, 10, 20, 30}, a2[] = {100, 100, 100},
a3[] = {37, 12, 28, 9, 100, 56, 80, 5, 12}, rs1, rs2, rs3;
int *art1 = arrayRankTransform(a1, ARRAY_SIZE(a1), &rs1);
int *art2 = arrayRankTransform(a2, ARRAY_SIZE(a2), &rs2);
int *art3 = arrayRankTransform(a3, ARRAY_SIZE(a3), &rs3);
for (int i = 0; i < rs1; i++)
printf("%d ", art1[i]); // expect: 4 1 2 3
printf("\n");
for (int i = 0; i < rs2; i++)
printf("%d ", art2[i]); // expect: 1 1 1
printf("\n");
for (int i = 0; i < rs3; i++)
printf("%d ", art3[i]); // expect: 5 3 4 2 8 6 7 1 3
printf("\n");
free(art1), free(art2), free(art3);
}
|