代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个下标从 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
中不存在。我们先用哈希表 $d$ 记录数组 nums
中每个数字的下标,然后遍历操作数组 operations
,对于每个操作 $[a, b]$,我们将 $a$ 在 nums
中的下标 $d[a]$ 对应的数字替换为 $b$,并更新 $d$ 中 $b$ 的下标为 $d[a]$。
最后返回 nums
即可。
时间复杂度 $O(n + m)$,空间复杂度 $O(n)$。其中 $n$ 和 $m$ 分别是数组 nums
和 operations
的长度。
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:
nums[d[a]] = b
d[b] = d[a]
return nums
class Solution {
public int[] arrayChange(int[] nums, int[][] operations) {
Map<Integer, Integer> d = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
d.put(nums[i], i);
}
for (var op : operations) {
int a = op[0], b = op[1];
nums[d.get(a)] = b;
d.put(b, d.get(a));
}
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 a = op[0], b = op[1];
nums[d[a]] = b;
d[b] = d[a];
}
return nums;
}
};
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]
nums[d[a]] = b
d[b] = d[a]
}
return nums
}
function arrayChange(nums: number[], operations: number[][]): number[] {
const d = new Map(nums.map((v, i) => [v, i]));
for (const [a, b] of operations) {
nums[d.get(a)] = b;
d.set(b, d.get(a));
}
return nums;
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。