2295. 替换数组中的元素

题目描述

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

解法

方法一：哈希表

我们先用哈希表 \(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}\) 的长度。

Python3JavaC++GoTypeScript

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

class Solution {
    public int[] arrayChange(int[] nums, int[][] operations) {
        int n = nums.length;
        Map<Integer, Integer> d = new HashMap<>(n);
        for (int i = 0; i < n; ++i) {
            d.put(nums[i], i);
        }
        for (var op : operations) {
            int x = op[0], y = op[1];
            nums[d.get(x)] = y;
            d.put(y, d.get(x));
        }
        return nums;
    }
}

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

func arrayChange(nums []int, operations [][]int) []int {
    d := map[int]int{}
    for i, x := range nums {
        d[x] = i
    }
    for _, op := range operations {
        x, y := op[0], op[1]
        nums[d[x]] = y
        d[y] = d[x]
    }
    return nums
}

function arrayChange(nums: number[], operations: number[][]): number[] {
    const d: Map<number, number> = new Map(nums.map((x, i) => [x, i]));
    for (const [x, y] of operations) {
        nums[d.get(x)!] = y;
        d.set(y, d.get(x)!);
    }
    return nums;
}

2295. 替换数组中的元素

题目描述

解法

方法一：哈希表

评论