leetcode
leetcode 2001 ~ 2050
替换数组中的元素

替换数组中的元素

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
在解题思路中,为什么选择从后向前遍历操作数组而不是从前向后进行操作?
从后向前遍历操作数组是为了正确处理多级或链式替换的情况。如果从前向后遍历,每次替换只能保证当前步骤的正确性,但无法保证这种替换关系在之后的操作中不被覆盖。例如,对于操作列表 [a, b] 和 [b, c],如果从前向后遍历,第一步将 a 替换为 b,第二步将 b 替换为 c,但这并不反映出 a 应该直接替换为 c 的最终结果。从后向前遍历则可以直接将 b 替换为 c,然后 a 替换为 c,从而保持了替换的连贯性和最终正确性。
🦆
在构建哈希表时,使用了`mp.get(y, y)`来更新映射,这种方法是如何确保每个数字都能正确映射到最终的值的?
在构建哈希表时使用 `mp.get(y, y)` 方法的目的是查找 y 的最终替换值。如果 y 已经是之前操作的目标,并且已经有了新的替换值,则 `mp.get(y)` 会返回这个新的替换值。如果没有,就返回 y 本身,意味着 y 直接替换为它自己(即没有进一步的替换)。这样处理可以确保即使在多级替换的情况下,每个元素都能被正确地映射到其最终的目标值。
🦆
题目中提到了操作列表中的替换都是有效的,这是否意味着在实现时不需要对操作的有效性进行额外的检查?
是的,题目说明操作列表中的所有替换都是有效的,这意味着在实现算法时,我们可以假设每个操作都不会导致错误或无效的输入。因此,不需要编写额外的代码来检查操作的有效性,如检查操作中的数字是否存在于数组中。这简化了实现并可以提高代码的运行效率。
🦆
在将`nums`数组中的每个元素替换成映射值时,是否有可能出现某些元素在哈希表中没有对应映射而导致错误替换?
在这种实现方法中,即使某些元素在哈希表中没有直接的映射,也不会导致错误替换。当使用 `mp.get(num, num)` 方法时,如果 `num` 没有在哈希表中找到对应的映射,该方法会返回 `num` 本身,即元素保持不变。这确保了即使没有映射信息,元素也不会被错误地替换,而是保持原样。

相关问题