aboutsummaryrefslogtreecommitdiff
path: root/rank_transform_array.c
blob: d8450e44a13f6090111434a412bb379e84526efa (plain)
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);
}