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 <= 10^5
  • 1 <= moveFrom.length <= 10^5
  • moveFrom.length == moveTo.length
  • 1 <= nums[i], moveFrom[i], moveTo[i] <= 10^9
  • 测试用例保证在进行第 i 步操作时，moveFrom[i] 处至少有一个弹珠。

解题思路

这道题的核心思路是使用哈希集合来跟踪弹珠的位置。

基本思路：

  1. 我们只需要关心哪些位置有弹珠，而不需要关心每个位置具体有多少个弹珠
  2. 使用集合存储所有有弹珠的位置
  3. 对于每次移动操作，将起始位置从集合中删除，将目标位置添加到集合中
  4. 最后将集合转换为排序的数组返回

算法步骤：

  1. 将初始弹珠位置全部加入集合中
  2. 遍历每个移动操作 (moveFrom[i], moveTo[i])：
    • 从集合中删除 moveFrom[i]
    • 向集合中添加 moveTo[i]
  3. 将集合转换为排序数组返回

优化点：

  • 使用集合自动去重，避免重复位置
  • 只关心位置是否有弹珠，不需要计算具体数量
  • 最后一次性排序，而不是在操作过程中维护有序性

这种方法的时间复杂度主要来自于集合操作和最终的排序，空间复杂度取决于不同位置的数量。

代码实现

class Solution {
public:
    vector<int> relocateMarbles(vector<int>& nums, vector<int>& moveFrom, vector<int>& moveTo) {
        unordered_set<int> positions;
        
        // 添加初始位置
        for (int num : nums) {
            positions.insert(num);
        }
        
        // 执行移动操作
        for (int i = 0; i < moveFrom.size(); i++) {
            positions.erase(moveFrom[i]);
            positions.insert(moveTo[i]);
        }
        
        // 转换为排序数组
        vector<int> result(positions.begin(), positions.end());
        sort(result.begin(), result.end());
        
        return result;
    }
};

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.remove(from_pos)
            positions.add(to_pos)
        
        return sorted(positions)

public class Solution {
    public IList<int> RelocateMarbles(int[] nums, int[] moveFrom, int[] moveTo) {
        HashSet<int> positions = new HashSet<int>(nums);
        
        for (int i = 0; i < moveFrom.Length; i++) {
            positions.Remove(moveFrom[i]);
            positions.Add(moveTo[i]);
        }
        
        List<int> result = new List<int>(positions);
        result.Sort();
        
        return result;
    }
}

var relocateMarbles = function(nums, moveFrom, moveTo) {
    const positions = new Set(nums);
    
    for (let i = 0; i < moveFrom.length; i++) {
        positions.delete(moveFrom[i]);
        positions.add(moveTo[i]);
    }
    
    return Array.from(positions).sort((a, b) => a - b);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + m + k log k)n为nums长度，m为移动操作次数，k为最终不同位置数量。集合操作O(1)，最终排序O(k log k)
空间复杂度O(k)k为不同位置的数量，用于存储集合和结果数组