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^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 中不存在

解题思路

这道题要求我们对数组进行一系列替换操作，关键是如何高效地定位和替换元素。

思路分析

基本思路：

  • 最直接的方法是对每个操作遍历数组找到要替换的元素，但这样时间复杂度为 O(n×m)，在数据规模较大时会超时
  • 更好的方法是使用哈希表记录每个数字在数组中的位置，这样可以在 O(1) 时间内定位元素

哈希表优化：

  1. 先遍历原数组，建立数字到下标的映射关系
  2. 对每个操作 [old, new]：
    • 通过哈希表快速找到 old 在数组中的位置
    • 将该位置的值替换为 new
    • 更新哈希表：删除 old 的映射，添加 new 的映射

这种方法的时间复杂度为 O(n + m)，空间复杂度为 O(n)，是最优解法。

注意事项：

  • 题目保证每次操作中的 old 值一定存在，new 值一定不存在，简化了边界情况的处理
  • 哈希表需要同步更新，确保后续操作能正确找到被替换后的新值

代码实现

class Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        unordered_map<int, int> pos;
        for (int i = 0; i < nums.size(); i++) {
            pos[nums[i]] = i;
        }
        
        for (auto& op : operations) {
            int old_val = op[0];
            int new_val = op[1];
            int index = pos[old_val];
            
            nums[index] = new_val;
            pos.erase(old_val);
            pos[new_val] = index;
        }
        
        return nums;
    }
};

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        pos = {num: i for i, num in enumerate(nums)}
        
        for old_val, new_val in operations:
            index = pos[old_val]
            nums[index] = new_val
            del pos[old_val]
            pos[new_val] = index
        
        return nums

public class Solution {
    public int[] ArrayChange(int[] nums, int[][] operations) {
        Dictionary<int, int> pos = new Dictionary<int, int>();
        for (int i = 0; i < nums.Length; i++) {
            pos[nums[i]] = i;
        }
        
        foreach (var op in operations) {
            int oldVal = op[0];
            int newVal = op[1];
            int index = pos[oldVal];
            
            nums[index] = newVal;
            pos.Remove(oldVal);
            pos[newVal] = index;
        }
        
        return nums;
    }
}

var arrayChange = function(nums, operations) {
    const pos = new Map();
    for (let i = 0; i < nums.length; i++) {
        pos.set(nums[i], i);
    }
    
    for (const [oldVal, newVal] of operations) {
        const index = pos.get(oldVal);
        nums[index] = newVal;
        pos.delete(oldVal);
        pos.set(newVal, index);
    }
    
    return nums;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n + m)
空间复杂度O(n)

其中 n 是数组长度，m 是操作次数。时间复杂度中，O(n) 用于建立哈希表，O(m) 用于执行所有操作。空间复杂度主要来自哈希表存储所有元素的位置信息。

相关题目