What is the time complexity of replacing elements in an array using a hash map?

The time complexity of each replacement operation is O(1), so the overall time complexity for m operations is O(m).

How does a hash map help solve the problem efficiently?

The hash map provides O(1) time complexity for looking up the index of the element to replace, ensuring fast replacements for each operation.

What is the space complexity for this problem?

The space complexity is O(n), where n is the number of distinct elements in the array, due to the hash map storing the index of each element.

Can the solution be optimized further for larger inputs?

The solution is already efficient with O(1) time complexity per operation, so optimizing further would likely require focusing on the overall system architecture rather than the algorithm itself.

How does the pattern of array scanning plus hash lookup apply to this problem?

This pattern allows for efficient direct access to array elements that need to be replaced, ensuring that each operation is performed in constant time.

#2295

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

替换数组中的元素

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

数组哈希表模拟

题目描述

给你一个下标从 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 中不存在。

lightbulb

解题思路

方法一：哈希表

我们先用哈希表 $d$ 记录数组 $\textit{nums}$ 中每个数字的下标，然后遍历操作数组 $\textit{operations}$ ，对于每个操作 $[x, y]$ ，我们将 $x$ 在 $\textit{nums}$ 中的下标 $d[x]$ 对应的数字替换为 $y$ ，并更新 $d$ 中 $y$ 的下标为 $d[x]$ 。

最后返回 $\textit{nums}$ 即可。

时间复杂度 $O(n + m)$ ，空间复杂度 $O(n)$ 。其中 $n$ 和 $m$ 分别是数组 $\textit{nums}$ 的长度和操作数组 $\textit{operations}$ 的长度。

1

2

3

4

5

6

7

8

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate identify the need for a hash map to optimize lookups?
question_mark
Does the candidate recognize the importance of maintaining constant time complexity for updates?
question_mark
How well does the candidate handle large inputs with the given constraints?

warning

常见陷阱

外企场景

error
Not using a hash map, leading to inefficient scanning for each operation.
error
Forgetting to update the array after each operation, causing incorrect results.
error
Overcomplicating the solution by attempting to optimize prematurely without considering basic functionality first.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if we were given an array with duplicate elements? How would the solution change?
arrow_right_alt
How would the solution be affected if the replacement values could already exist in the array?
arrow_right_alt
What if the number of operations were much larger than the number of elements in the array?

help

常见问题

外企场景

继续练习

#2352 相等行列对 #2357 使数组中所有元素都等于零 #2365 任务调度器 II