侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【哈希表】替换数组中的元素

GabrielxD
2022-06-05 / 0 评论 / 0 点赞 / 28 阅读 / 541 字 / 正在检测是否收录...

题目

6092. 替换数组中的元素


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

解题

方法一:哈希表

思路

维护一个哈希表,键是数组中元素,值是对应其索引。遍历所有操作,对于每个操作直接从哈希表里取索引然后修改数组即可,修改完后也要更新哈希表里的对应关系。

代码

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

评论区