LeetCode·每日一题·1331.数组序号转换·离散化

链接：https://leetcode.cn/problems/rank-transform-of-an-array/solution/by-xun-ge-v-njcw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

 

示例

 

思路

对应哈希算法还不是特别熟悉的，可以看下方链接学习：
哈希算法详解

解题思路
对于本题，其实就是对数组元素进行离散化处理，存在的意义在于，当我们遇到值域非常大的数组时，我们想对这个数组进行处理，但是在处理过程中我们只关心元素的大小关系，并不关心实际值，但是值域非常大又会影响我们使用一些好的数据结构处理，比如线段树。。。那么此时就需要对数组元素进行离散化。比如数组[1,22,333,4444,55555]，在我们只关心元素大小时，其实和[1,2,3,4,5]是等价的。

具体实现
先对数组元素进行升序处理。然后将数组元素作为哈希key值，存入哈希表，并且打上标记，再遍历原始数组，将对应数组离散化结果存入对应位置。

代码

typedef struct {//定义散列表
    int key;
    int val;
    UT_hash_handle hh;
} HashItem;

static inline int cmp(const void *pa, const void *pb) {//升序子函数
    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);//初始化变量
    HashItem *ranks = NULL;//定义哈希表头结点
    int n = 1;
    for (int i = 0; i < arrSize; i++) {//遍历升序后的数组，并加入到哈希表中
        HashItem *pEntry = NULL;//定义哈希元素
        HASH_FIND_INT(ranks, &sortedArr[i], pEntry);//查询元素是否已经存在哈希表中
        if (pEntry == NULL) {//不存在，申请节点，存入哈希表
            pEntry = (HashItem *)malloc(sizeof(HashItem));
            pEntry->key = sortedArr[i];
            pEntry->val = n++;//打上标记
            HASH_ADD_INT(ranks, key, pEntry);//添加到哈希表
        }//存在时因为相同元素标记相同，所以不需要处理
    }
    for (int i = 0; i < arrSize; i++) {//遍历原始数组
        HashItem *pEntry = NULL;
        HASH_FIND_INT(ranks, &arr[i], pEntry);//寻找原始数组元素对应的标记
        ans[i] = pEntry->val;
    }
    *returnSize = arrSize;
    HashItem *cur, *tmp;
    HASH_ITER(hh, ranks, cur, tmp) {//销毁哈希表
        HASH_DEL(ranks, cur);  
        free(cur);             
    }
    free(sortedArr);
    return ans;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/rank-transform-of-an-array/solution/by-xun-ge-v-njcw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间空间复杂度