Leetcode · daily question · 1331. array sequence number conversion · discretization

link ：https://leetcode.cn/problems/rank-transform-of-an-array/solution/by-xun-ge-v-njcw/
source ： Power button （LeetCode）
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source . 

subject

 

Example

 

Ideas

The corresponding hash algorithm is not particularly familiar , You can see the link below to learn ：
Hash algorithm details

Their thinking
For this question , In fact, it is to discretize the array elements , The meaning of being is , When we encounter an array with a very large range of values , We want to process this array , But in the process of processing, we only care about the size relationship of elements , Don't care about the actual value , However, a very large range of values will affect our use of some good data structures , Such as line segment tree ... At this time, we need to discretize the array elements . For example, array [1,22,333,4444,55555], When we only care about the size of elements , Actually sum [1,2,3,4,5] It is equivalent. .

Concrete realization
First, the array elements are processed in ascending order . Then take the array elements as hashes key value , Save to hash table , And marked , Then traverse the original array , Store the discretization result of the corresponding array in the corresponding position .

Code

typedef struct {// Define hash table 
    int key;
    int val;
    UT_hash_handle hh;
} HashItem;

static inline int cmp(const void *pa, const void *pb) {// Ascending subfunction 
    return *(int *)pa - *(int *)pb;
}

int* arrayRankTransform(int* arr, int arrSize, int* returnSize) {
    int *sortedArr = (int *)malloc(sizeof(int) * arrSize);
    int *ans = (int *)malloc(sizeof(int) * arrSize);
    memcpy(sortedArr, arr, sizeof(int) * arrSize);
    qsort(sortedArr, arrSize, sizeof(int), cmp);// Initialize variable 
    HashItem *ranks = NULL;// Define the hash header node 
    int n = 1;
    for (int i = 0; i < arrSize; i++) {// Traverse the ascending array , And add it to the hash table 
        HashItem *pEntry = NULL;// Define hash elements 
        HASH_FIND_INT(ranks, &sortedArr[i], pEntry);// Query whether the element already exists in the hash table 
        if (pEntry == NULL) {// non-existent , Application node , Save to hash table 
            pEntry = (HashItem *)malloc(sizeof(HashItem));
            pEntry->key = sortedArr[i];
            pEntry->val = n++;// Mark 
            HASH_ADD_INT(ranks, key, pEntry);// Add to hash table 
        }// It exists because the same elements are marked the same , So there's no need to deal with 
    }
    for (int i = 0; i < arrSize; i++) {// Traverse the original array 
        HashItem *pEntry = NULL;
        HASH_FIND_INT(ranks, &arr[i], pEntry);// Find the tag corresponding to the original array element 
        ans[i] = pEntry->val;
    }
    *returnSize = arrSize;
    HashItem *cur, *tmp;
    HASH_ITER(hh, ranks, cur, tmp) {// Destroy hash table 
        HASH_DEL(ranks, cur);  
        free(cur);             
    }
    free(sortedArr);
    return ans;
}


 author ：xun-ge-v
 link ：https://leetcode.cn/problems/rank-transform-of-an-array/solution/by-xun-ge-v-njcw/
 source ： Power button （LeetCode）
 The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Time and space complexity