【C语言刷LeetCode】2295. 替换数组中的元素(M)

【

给你一个下标从 0 开始的数组 nums ，它包含 n 个 互不相同 的正整数。请你对这个数组执行 m 个操作，在第 i 个操作中，你需要将数字 operations[i][0] 替换成 operations[i][1] 。

题目保证在第 i 个操作中：

operations[i][0] 在 nums 中存在。
operations[i][1] 在 nums 中不存在。
请你返回执行完所有操作后的数组。

示例 1：

输入：nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
输出：[3,2,7,1]
解释：我们对 nums 执行以下操作：
- 将数字 1 替换为 3 。nums 变为 [3,2,4,6] 。
- 将数字 4 替换为 7 。nums 变为 [3,2,7,6] 。
- 将数字 6 替换为 1 。nums 变为 [3,2,7,1] 。
返回最终数组 [3,2,7,1] 。
示例 2：

输入：nums = [1,2], operations = [[1,3],[2,1],[3,2]]
输出：[2,1]
解释：我们对 nums 执行以下操作：
- 将数字 1 替换为 3 。nums 变为 [3,2] 。
- 将数字 2 替换为 1 。nums 变为 [3,1] 。
- 将数字 3 替换为 2 。nums 变为 [2,1] 。
返回最终数组 [2,1] 。
 

提示：

n == nums.length
m == operations.length
1 <= n, m <= 105
nums 中所有数字 互不相同 。
operations[i].length == 2
1 <= nums[i], operations[i][0], operations[i][1] <= 106
在执行第 i 个操作时，operations[i][0] 在 nums 中存在。
在执行第 i 个操作时，operations[i][1] 在 nums 中不存在。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/replace-elements-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

】

这次hash要替换key,所以需要先删除，再添加的操作

typedef struct {
    int key;
    int idx;
    UT_hash_handle hh;
} UTHASH;

int Cmp (UTHASH *a, UTHASH *b) 
{
    return a->idx - b->idx;
}

int* arrayChange(int* nums, int numsSize, int** operations, int operationsSize, int* operationsColSize, int* returnSize){
    UTHASH *mymap = NULL;
    int i;
    int *retarr = malloc(sizeof(int) * numsSize);

    for (i = 0; i < numsSize; i++) {
        UTHASH *new = malloc(sizeof(UTHASH)); 
        new->key = nums[i];
        new->idx = i;
        HASH_ADD_INT(mymap, key, new); // 每个元素互不相同，所以直接添加
    }

    for (i = 0; i < operationsSize; i++) {
        int key = operations[i][0];
        UTHASH *find = NULL;
        HASH_FIND_INT(mymap, &key, find); // 按照题意肯定能找到
        UTHASH *new = malloc(sizeof(UTHASH));
        new->key = operations[i][1];
        new->idx = find->idx;
        HASH_DEL(mymap, find); // 删掉这个节点
        HASH_ADD_INT(mymap, key, new); // 把新节点加进去
    }

    HASH_SORT(mymap,Cmp); // 排序

    UTHASH *cur, *tmp;
    int idx = 0;
    HASH_ITER(hh, mymap, cur, tmp) {
        retarr[idx++] = cur->key;
    }

    *returnSize = numsSize;
    return retarr;
}

/*
UTHASH 找到key后直接把key修改需要先用HASH_DEL删掉，再ADD

*/