README.md

2295. 替换数组中的元素

English Version

题目描述

给你一个下标从 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 <= 105
• nums 中所有数字 互不相同 。
• operations[i].length == 2
• 1 <= nums[i], operations[i][0], operations[i][1] <= 106
• 在执行第 i 个操作时，operations[i][0] 在 nums 中存在。
• 在执行第 i 个操作时，operations[i][1] 在 nums 中不存在。

解法

方法一：哈希表

Python3

class Solution:
    def arrayChange(self, nums: List[int], operations: List[List[int]]) -> List[int]:
        d = {v: i for i, v in enumerate(nums)}
        for a, b in operations:
            idx = d[a]
            d.pop(a)
            d[b] = idx
        ans = [0] * len(nums)
        for v, i in d.items():
            ans[i] = v
        return ans

Java

class Solution {
    public int[] arrayChange(int[] nums, int[][] operations) {
        int n = nums.length;
        Map<Integer, Integer> d = new HashMap<>();
        for (int i = 0; i < n; ++i) {
            d.put(nums[i], i);
        }
        for (int[] op : operations) {
            int a = op[0], b = op[1];
            int idx = d.get(a);
            d.remove(a);
            d.put(b, idx);
        }
        int[] ans = new int[n];
        d.forEach((v, i) -> { ans[i] = v; });
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> arrayChange(vector<int>& nums, vector<vector<int>>& operations) {
        int n = nums.size();
        unordered_map<int, int> d;
        for (int i = 0; i < n; ++i) d[nums[i]] = i;
        for (auto& op : operations) {
            int a = op[0], b = op[1];
            int idx = d[a];
            d.erase(a);
            d[b] = idx;
        }
        vector<int> ans(n);
        for (auto& [v, i] : d) ans[i] = v;
        return ans;
    }
};

Go

func arrayChange(nums []int, operations [][]int) []int {
	d := map[int]int{}
	for i, v := range nums {
		d[v] = i
	}
	for _, op := range operations {
		a, b := op[0], op[1]
		idx := d[a]
		delete(d, a)
		d[b] = idx
	}
	ans := make([]int, len(nums))
	for v, i := range d {
		ans[i] = v
	}
	return ans
}

TypeScript

function arrayChange(nums: number[], operations: number[][]): number[] {
    const n = nums.length;
    let hashMap = new Map(nums.map((v, i) => [v, i]));
    for (let [oldVal, newVal] of operations) {
        let idx = hashMap.get(oldVal);
        hashMap.delete(oldVal);
        hashMap.set(newVal, idx);
    }
    let ans = new Array(n);
    for (let [val, key] of hashMap.entries()) {
        ans[key] = val;
    }
    return ans;
}

...