重新放置石块

标签: 数组 哈希表 排序 模拟

难度: Medium

给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度 相等 下标从 0 开始的整数数组 moveFrom 和 moveTo 。

在 moveFrom.length 次操作内，你可以改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位置 moveTo[i] 。

完成这些操作后，请你按升序返回所有 有 石块的位置。

注意：

  • 如果一个位置至少有一个石块，我们称这个位置 有 石块。
  • 一个位置可能会有多个石块。

示例 1：

输入：nums = [1,6,7,8], moveFrom = [1,7,2], moveTo = [2,9,5]
输出：[5,6,8,9]
解释：一开始，石块在位置 1,6,7,8 。
第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，位置 2,6,7,8 有石块。
第 i = 1 步操作中，我们将位置 7 处的石块移到位置 9 处，位置 2,6,8,9 有石块。
第 i = 2 步操作中，我们将位置 2 处的石块移到位置 5 处，位置 5,6,8,9 有石块。
最后，至少有一个石块的位置为 [5,6,8,9] 。

示例 2：

输入：nums = [1,1,3,3], moveFrom = [1,3], moveTo = [2,2]
输出：[2]
解释：一开始，石块在位置 [1,1,3,3] 。
第 i = 0 步操作中，我们将位置 1 处的石块移到位置 2 处，有石块的位置为 [2,2,3,3] 。
第 i = 1 步操作中，我们将位置 3 处的石块移到位置 2 处，有石块的位置为 [2,2,2,2] 。
由于 2 是唯一有石块的位置，我们返回 [2] 。

提示：

  • 1 <= nums.length <= 105
  • 1 <= moveFrom.length <= 105
  • moveFrom.length == moveTo.length
  • 1 <= nums[i], moveFrom[i], moveTo[i] <= 109
  • 测试数据保证在进行第 i 步操作时，moveFrom[i] 处至少有一个石块。

Submission

运行时间: 77 ms

内存: 34.6 MB

from typing import List

class Solution:
    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
        positions = set(nums)  # Initialize a set with the initial positions

        # Iterate over the move operations
        for from_pos, to_pos in zip(moveFrom, moveTo):
            positions.discard(from_pos)  # Remove the stone from the previous position
            positions.add(to_pos)  # Add the stone to the new position

        return sorted(positions)  # Convert the set to a sorted list and return it

solution = Solution()
nums = [1, 6, 7, 8]
moveFrom = [1, 7, 2]
moveTo = [2, 9, 5]
result = solution.relocateMarbles(nums, moveFrom, moveTo)
print(result)  # Output: [5, 6, 8, 9]

Explain

这个解决方案使用了一个集合（Set）来跟踪所有石块的位置。初始时，将 nums 数组中所有的位置加入到集合中，代表石块的初始位置。然后，通过遍历 moveFrom 和 moveTo 数组，对于每一对操作（从 moveFrom[i] 移动到 moveTo[i]），先从集合中移除 moveFrom[i]（因为石块从此位置移走），然后将 moveTo[i] 加入到集合中（石块移动到新位置）。因为集合自动处理重复的元素，所以即使多次移动到同一个位置也不会有问题。最后，将集合转换为有序数组后返回，这样可以得到所有有石块的位置的升序列表。

时间复杂度: O(n + m + k log k)

空间复杂度: O(n + m)

from typing import List

class Solution:
    def relocateMarbles(self, nums: List[int], moveFrom: List[int], moveTo: List[int]) -> List[int]:
        positions = set(nums)  # 使用集合存储所有有石块的位置

        # 遍历所有移动操作
        for from_pos, to_pos in zip(moveFrom, moveTo):
            positions.discard(from_pos)  # 从集合中移除旧位置
            positions.add(to_pos)  # 向集合中添加新位置

        return sorted(positions)  # 返回有石块的位置的升序列表

solution = Solution()
nums = [1, 6, 7, 8]
moveFrom = [1, 7, 2]
moveTo = [2, 9, 5]
result = solution.relocateMarbles(nums, moveFrom, moveTo)
print(result)  # 输出: [5, 6, 8, 9]

Explore

在这个算法中，我们假设每个位置最初只有一个石块，且每次移动操作只涉及一个石块。因此，当从moveFrom[i]位置移动石块时，我们认为该位置变为空，所以需要从集合中移除该位置。如果实际情况中某个位置可以有多个石块，那么这种假设就不成立，需要修改算法以记录每个位置的石块数量。

如果moveFrom数组中的某个位置原本就不存在于nums中，那么尝试从集合中移除该位置将不会有任何效果，因为集合中本来就没有这个元素。这种情况不会影响最终输出结果，因为最终输出的是集合中仍然存在的元素（即石块的最终位置）。

集合是一种数据结构，可以自动处理重复的元素，即它不会存储重复的值。当尝试向集合中添加一个已经存在的元素时，集合将不会再次添加该元素，保持元素的唯一性。因此，即使算法中多次将石块移动到同一个位置，集合中该位置只会被记录一次，避免了重复记录的问题。

集合是一个无序的数据结构，如果需要按特定顺序（例如升序）查看或返回集合中的元素，必须对其进行排序。虽然排序操作有一定的计算成本，但由于集合的无序性质，排序是实现元素有序输出的直接和简单方法。在没有特定要求进行高效排序或数据量非常大的情况下，直接使用排序是一个有效且实用的选择。