替换数组中的元素

难度: Medium

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

Submission

运行时间: 106 ms

内存: 54.9 MB

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) # mp.setdefault(x, y)
        
        return [mp.get(num, num) for num in nums]

Explain

这个题解使用了一个哈希表来跟踪每个数字最终应该被替换成什么数字。首先，对操作列表进行逆序遍历。对于每个操作 [x, y]，如果 y 已经在哈希表中作为键存在，那么将 x 映射到 y 映射的值，否则将 x 直接映射到 y。这样做是为了处理链式替换，例如连续的替换操作 [a, b] 和 [b, c] 应该最终导致 a 替换为 c。这一步确保了每个数字的最终替换值可以在一次查找中直接得到。在构建完映射后，再遍历原数组，将每个数字替换为其映射值（如果存在映射的话），否则保持不变。

时间复杂度: O(m + n)

空间复杂度: O(m)

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) # 如果 y 是一个中间值，则继续追踪最终值
        
        # 根据映射表替换数组中的元素
        return [mp.get(num, num) for num in nums]

Explore

从后向前遍历操作数组是为了正确处理多级或链式替换的情况。如果从前向后遍历，每次替换只能保证当前步骤的正确性，但无法保证这种替换关系在之后的操作中不被覆盖。例如，对于操作列表 [a, b] 和 [b, c]，如果从前向后遍历，第一步将 a 替换为 b，第二步将 b 替换为 c，但这并不反映出 a 应该直接替换为 c 的最终结果。从后向前遍历则可以直接将 b 替换为 c，然后 a 替换为 c，从而保持了替换的连贯性和最终正确性。

在构建哈希表时使用 `mp.get(y, y)` 方法的目的是查找 y 的最终替换值。如果 y 已经是之前操作的目标，并且已经有了新的替换值，则 `mp.get(y)` 会返回这个新的替换值。如果没有，就返回 y 本身，意味着 y 直接替换为它自己（即没有进一步的替换）。这样处理可以确保即使在多级替换的情况下，每个元素都能被正确地映射到其最终的目标值。

是的，题目说明操作列表中的所有替换都是有效的，这意味着在实现算法时，我们可以假设每个操作都不会导致错误或无效的输入。因此，不需要编写额外的代码来检查操作的有效性，如检查操作中的数字是否存在于数组中。这简化了实现并可以提高代码的运行效率。

在这种实现方法中，即使某些元素在哈希表中没有直接的映射，也不会导致错误替换。当使用 `mp.get(num, num)` 方法时，如果 `num` 没有在哈希表中找到对应的映射，该方法会返回 `num` 本身，即元素保持不变。这确保了即使没有映射信息，元素也不会被错误地替换，而是保持原样。