How can I solve the 'Relocate Marbles' problem efficiently?

By using array scanning combined with a set or hash map to manage unique positions, you can simulate the marble movements efficiently, and then sort the final list.

What is the time complexity for 'Relocate Marbles'?

The time complexity is O(n + m log m), where n is the length of `nums` and m is the number of unique final positions after all moves.

Can this problem be solved using sorting?

Sorting is used at the end to return the list of occupied positions in sorted order, but the main challenge is efficiently simulating the marble movements using array scanning and hash lookup.

What is the purpose of using a set in the solution?

A set is used to efficiently manage unique positions of marbles, preventing duplicates and ensuring that only unique positions are considered in the final result.

What are some common mistakes in solving 'Relocate Marbles'?

Common mistakes include failing to manage duplicate positions correctly, not using sets for efficient lookups, and overcomplicating the sorting step.

#2766

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

重新放置石块

给你一个下标从 0 开始的整数数组 nums ，表示一些石块的初始位置。再给你两个长度相等下标从 0 开始的整数数组 moveFrom 和 moveTo 。在 moveFrom.length 次操作内，你将改变石块的位置。在第 i 次操作中，你将位置在 moveFrom[i] 的所有石块移到位…

数组哈希表排序模拟

题目描述

给你一个下标从 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⁵
1 <= moveFrom.length <= 10⁵
moveFrom.length == moveTo.length
1 <= nums[i], moveFrom[i], moveTo[i] <= 10⁹
测试数据保证在进行第 i 步操作时，moveFrom[i] 处至少有一个石块。

lightbulb

解题思路

方法一：哈希表

我们用一个哈希表 $pos$ 记录所有有石块的位置，初始时 $pos$ 中包含 $nums$ 中的所有元素。然后我们遍历 $moveFrom$ 和 $moveTo$ ，每次将 $moveFrom[i]$ 从 $pos$ 中移除，再将 $moveTo[i]$ 添加到 $pos$ 中。最后我们将 $pos$ 中的元素排序后返回即可。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def relocateMarbles(
        self, nums: List[int], moveFrom: List[int], moveTo: List[int]
    ) -> List[int]:
        pos = set(nums)
        for f, t in zip(moveFrom, moveTo):
            pos.remove(f)
            pos.add(t)
        return sorted(pos)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate efficiently handle updates to the positions of multiple marbles in each move?
question_mark
Does the candidate consider using a set or hash map to manage the unique positions of marbles?
question_mark
Is the candidate able to optimize the sorting step to avoid unnecessary computation?

warning

常见陷阱

外企场景

error
Failing to account for the possibility of multiple marbles being moved to the same position.
error
Not using efficient data structures like sets to handle unique positions and optimize the move process.
error
Overcomplicating the sorting step or failing to sort the final result efficiently.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handle a case where `nums`, `moveFrom`, and `moveTo` have large sizes and test for performance.
arrow_right_alt
Consider scenarios where marbles can move from a position to the same position multiple times, ensuring no unnecessary changes are made.
arrow_right_alt
Explore different ways of sorting the final list, such as using a priority queue or quicksort for optimization.

help

常见问题

外企场景

继续练习

#2593 标记所有元素后数组的分数 #3080 执行操作标记数组中的元素 #2402 会议室 III