【LeetCode】替换数组中的元素 Java 题解

2022 年 6 月 10 日
本文字数：1219 字
阅读完需：约 4 分钟

题目描述

给你一个下标从 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] 。 
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/replace-elements-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组题目，题目要求替换数组元素，并给出了需要替换的元素和替换后的元素。根据题目要求，我们首先可以使用暴力的方式解决，循环遍历 operations 数组，然后对 nums 数组进行操作。
暴力的方法会对 nums 数组进行多次遍历，时间复杂度比较高，不能通过所有测试样例。
我们采用 hashmap 的数据结构，以空间换时间，记录每一个数值出现的索引位置，然后进行指定位置的替换，数组根据索引位置替换数值的时间复杂度是 O(1)。实现代码如下，供参考。

通过代码

class Solution {    public int[] arrayChange(int[] nums, int[][] operations) {        int n = nums.length;        Map<Integer, List<Integer>> map = new HashMap<>();        for (int j = 0; j < n; j++) {            List<Integer> idxList = map.getOrDefault(nums[j], new ArrayList<>());            idxList.add(j);            map.put(nums[j], idxList);        }                        for (int[] operation : operations) {            List<Integer> idxList = map.getOrDefault(operation[0], new ArrayList<>());            List<Integer> newIdxList = new ArrayList<>();                        for (int i = 0; i < idxList.size(); i++) {                nums[idxList.get(i)] = operation[1];                newIdxList.add(idxList.get(i));            }                        map.put(operation[0], new ArrayList<>());            map.put(operation[1], newIdxList);        }                return nums;    }}