2295. 替换数组中的元素

题目

给你一个下标从 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 <= 10^5
• nums 中所有数字 互不相同 。
• operations[i].length == 2
• 1 <= nums[i], operations[i][0], operations[i][1] <= 10^6
• 在执行第 i 个操作时，operations[i][0] 在 nums 中存在。
• 在执行第 i 个操作时，operations[i][1] 在 nums 中不存在。

解答

思路

由于 $1\le n,m\le {10}^5$，貌似会出现 $O(n^2)$ 的复杂度。但是题目要求：

• 输入的时候所有数字都是不同的
• 在执行操作的时候，原数字一定存在，操作后的数字一定不存在
• 因此每次只会操作一个数字，操作完之后数组 所有数字仍然是不同的

代码

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        idx = {num: i for i, num in enumerate(nums)}
        
        for x, y in operations:
            i = idx[x]
            nums[i] = y
            del idx[x]
            idx[y] = i
        
        return nums

其实这里的 del idx[x] 可以不用，因为：

• 如果 x == y 的话，那么 idx[y] = i 就直接覆盖掉了
• 如果 y != x 的话，那么说明 名义上 没有将 x 放到数组中，按照操作规范是不会出现这种操作的

思路：有重复数字

假如没有这些条例，例如对于：

nums = [...]

1 -> 2
2 -> 3
3 -> 4

nums = [4, 4, 4]

那么如何思考呢？我们可以记录一个映射 map[]，把原始值映射到新值上：

map[1] = 2
map[2] = 3
map[3] = 4

如果我们 倒序思考，对于操作 map[x] = y：

• 如果 map[] 中包含了 y，不妨设 map[y] = k，也就是 y 最后都要被赋值为 k
• 因此 map[x] = k，直接把 x 赋值为 k 就好，同时 x 进入 map[] 中
• 如果 map[] 中不包含 y，那么将其加入 map

好像 并查集 啊。实际上这就是类似并查集的过程，只不过不会出现并查集中 map[y] 再一次变为 j 的这种多次变化集合的情况。倒数第一次操作决定了 map[y] 的最终归宿，依次类推。

代码

Python 代码

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        mp = {}

        for x, y in reversed(operations):
            mp[x] = mp.get(y, y)
        
        return [mp.get(num, num) for num in nums]

C++ 代码

class Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        unordered_map<int, int> mp;
        int n = operations.size();

        for (int i = n - 1; i >= 0; i --) {
            auto& op = operations[i];
            int x = op[0];
            int y = op[1];

            mp[x] = mp.count(y) ? mp[y] : y;
        }

        for (auto& num: nums) {
            num = mp.count(num) ? mp[num] : num;
            // if (mp.count(num)) {
            //     num = mp[num];
            // }
        }

        return nums;
    }
};