关于算法:拉勾算法突击特训营3期完整无密

55次阅读

共计 1754 个字符，预计需要花费 5 分钟才能阅读完成。

leetcode 2295. Replace Elements in an Array
描述
You are given a 0-indexed array nums that consists of n distinct positive integers. Apply m operations to this array, where in the ith operation you replace the number operationsi with operationsi.
It is guaranteed that in the ith operation:
operationsi exists in nums.
operationsi does not exist in nums.
Return the array obtained after applying all the operations.
Example 1:
Input: nums = [1,2,4,6], operations = [[1,3],[4,7],[6,1]]
Output: [3,2,7,1]
Explanation: We perform the following operations on nums:

Replace the number 1 with 3. nums becomes [3,2,4,6].
Replace the number 4 with 7. nums becomes [3,2,7,6].
Replace the number 6 with 1. nums becomes [3,2,7,1].
We return the final array [3,2,7,1].
复制代码
Example 2:
Input: nums = [1,2], operations = [[1,3],[2,1],[3,2]]
Output: [2,1]
Explanation: We perform the following operations to nums:
Replace the number 1 with 3. nums becomes [3,2].
Replace the number 2 with 1. nums becomes [3,1].
Replace the number 3 with 2. nums becomes [2,1].
We return the array [2,1].
复制代码
Note:
n == nums.length
m == operations.length
<= n, m <= 10^5
All the values of nums are distinct.
operations[i].length == 2
<= nums[i], operationsi, operationsi <= 10^6
operationsi will exist in nums when applying the ith operation.
operationsi will not exist in nums when applying the ith operation.
复制代码
解析
根据题意，给定一个由 n 个不同的正整数组成的索引为 0 的数组 nums。对这个数组利用 m 个操作，在第 i 个操作中，将数字 operationsi 替换为 operationsi。
题目保障在第 i 次操作中：

operationi 存在于 nums 中
operationi 在 nums 中不存在

返回利用所有操作后失去的数组。
这道题其实按照题意就可能了，需要注意的地方是咱们要使用字典 d 来保存每个元素的索引，并且在进行操作之后将每个字符对应的索引进行更新即可。
工夫复杂度为 O(N)，空间复杂度为 O(N)。
解答
class Solution(object):

def arrayChange(self, nums, operations):
    """
    :type nums: List[int]
    :type operations: List[List[int]]
    :rtype: List[int]
    """
    N = len(operations)
    d = {}
    for i, c in enumerate(nums):
        d = i
    for i in range(N):
        x, y = operations[i]
        idx = d[x]
        nums[idx] = y
        d[y] = idx
    return nums

复制代码
运行后果
80 / 80 test cases passed.
Status: Accepted
Runtime: 1826 ms
Memory Usage: 73.6 MB

正文完