替换数组中的元素
难度:
标签:
题目描述
代码结果
运行时间: 106 ms, 内存: 54.9 MB
/*
* 思路:
* 1. 由于Java Stream操作并不擅长处理这样的修改操作,这里我们结合传统方法使用Stream。
* 2. 首先将数组转换为Stream进行处理,然后使用map替换元素。
* 3. 在操作过程中,我们依然使用HashMap来保持元素的索引。
*/
import java.util.Arrays;
import java.util.HashMap;
public class Solution {
public int[] arrayChange(int[] nums, int[][] operations) {
// 创建哈希表存储数字及其索引
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
// 使用Stream处理数组
return Arrays.stream(nums)
.map(num -> {
for (int[] operation : operations) {
if (num == operation[0]) {
int newNum = operation[1];
int index = map.get(num);
map.remove(num);
map.put(newNum, index);
return newNum;
}
}
return num;
}).toArray();
}
}
解释
方法:
这个题解使用了一个哈希表来跟踪每个数字最终应该被替换成什么数字。首先,对操作列表进行逆序遍历。对于每个操作 [x, y],如果 y 已经在哈希表中作为键存在,那么将 x 映射到 y 映射的值,否则将 x 直接映射到 y。这样做是为了处理链式替换,例如连续的替换操作 [a, b] 和 [b, c] 应该最终导致 a 替换为 c。这一步确保了每个数字的最终替换值可以在一次查找中直接得到。在构建完映射后,再遍历原数组,将每个数字替换为其映射值(如果存在映射的话),否则保持不变。
时间复杂度:
O(m + n)
空间复杂度:
O(m)
代码细节讲解
🦆
在解题思路中,为什么选择从后向前遍历操作数组而不是从前向后进行操作?
▷🦆
在构建哈希表时,使用了`mp.get(y, y)`来更新映射,这种方法是如何确保每个数字都能正确映射到最终的值的?
▷🦆
题目中提到了操作列表中的替换都是有效的,这是否意味着在实现时不需要对操作的有效性进行额外的检查?
▷🦆
在将`nums`数组中的每个元素替换成映射值时,是否有可能出现某些元素在哈希表中没有对应映射而导致错误替换?
▷