From 2c57d963fbbef6543d90a1ee08b13b5eee0813b0 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Tue, 1 Oct 2024 18:23:28 -0600 Subject: 1331. rank transform of an array --- rank_transform_array.c | 64 +++++++++++++++++++++++++++++++++++++++++++++++++ rank_transform_array.py | 28 ++++++++++++++++++++++ 2 files changed, 92 insertions(+) create mode 100644 rank_transform_array.c create mode 100644 rank_transform_array.py 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); +} diff --git a/rank_transform_array.py b/rank_transform_array.py new file mode 100644 index 0000000..5f6f860 --- /dev/null +++ b/rank_transform_array.py @@ -0,0 +1,28 @@ +# 1331. Rank Transform of an Array + +""" +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. +""" + + +class Solution(object): + def arrayRankTransform(self, arr): + """ + :type arr: List[int] + :rtype: List[int] + """ + rank = {} + for i in sorted(arr): + rank.setdefault(i, len(rank) + 1) + return map(rank.get, arr) + + +if __name__ == "__main__": + obj = Solution() + print(obj.arrayRankTransform(arr=[40, 10, 20, 30])) + print(obj.arrayRankTransform(arr=[100, 100, 100])) + print(obj.arrayRankTransform(arr=[37, 12, 28, 9, 100, 56, 80, 5, 12])) -- cgit v1.2.3