aboutsummaryrefslogtreecommitdiff
path: root/rank_transform_array.c
diff options
context:
space:
mode:
Diffstat (limited to 'rank_transform_array.c')
-rw-r--r--rank_transform_array.c64
1 files changed, 64 insertions, 0 deletions
diff --git a/rank_transform_array.c b/rank_transform_array.c
new file mode 100644
index 0000000..d8450e4
--- /dev/null
+++ b/rank_transform_array.c
@@ -0,0 +1,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);
+}