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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/replace-elements-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

害，T3没做出来，看着三千人做出来了，有点搞心态。

结果果然是自己想复杂了，没注意到题目关键信息「nums 中所有数字互不相同」，也就是说每次变换后所有数字都不相同。

那么，因为所有数字都不相同，便可以使用哈希表将每一个数字位置存下来。

然后遍历operations数组，记遍历的子数组为op。遍历过程中对于每一个op每次只会更改一个数字，在哈希表中获取op[0]的下标，然后将nums中将该位置修改为op[1]。同时，更新哈希表，去除op[0]键，增加op[1]键。借助哈希表，遍历一次operations就好了，时间复杂度10^6

代码

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