能否连接形成数组

标签: 数组 哈希表

难度: Easy

给你一个整数数组 arr ，数组中的每个整数 互不相同 。另有一个由整数数组构成的数组 pieces，其中的整数也 互不相同 。请你以 任意顺序 连接 pieces 中的数组以形成 arr 。但是，不允许 对每个数组 pieces[i] 中的整数重新排序。

如果可以连接 pieces 中的数组形成 arr ，返回 true ；否则，返回 false 。

示例 1：

输入：arr = [15,88], pieces = [[88],[15]]
输出：true
解释：依次连接 [15] 和 [88]

示例 2：

输入：arr = [49,18,16], pieces = [[16,18,49]]
输出：false
解释：即便数字相符，也不能重新排列 pieces[0]

示例 3：

输入：arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
输出：true
解释：依次连接 [91]、[4,64] 和 [78]

提示：

  • 1 <= pieces.length <= arr.length <= 100
  • sum(pieces[i].length) == arr.length
  • 1 <= pieces[i].length <= arr.length
  • 1 <= arr[i], pieces[i][j] <= 100
  • arr 中的整数 互不相同
  • pieces 中的整数 互不相同（也就是说，如果将 pieces 扁平化成一维数组，数组中的所有整数互不相同）

Submission

运行时间: 24 ms

内存: 16.7 MB

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        mapping = {}
        n = len(arr)
        for i in range(n):
            mapping[arr[i]] = i 
        vis = 0
        for piece in pieces:
            pre = None
            for p in piece:
                if (p not in mapping) or (pre != None and pre+1 != mapping[p]):
                    return False
                if(vis & (1 << mapping[p]) == 1):
                    return False 
                pre = mapping[p]
                vis |= (1 << mapping[p])
        return vis == 2**n-1

Explain

这个题解首先创建了一个字典 mapping，将数组 arr 的每个元素的值映射到它们在数组中的索引。然后，它使用一个位掩码 vis 来跟踪 arr 中每个元素是否被 pieces 数组正确地覆盖和连接。遍历 pieces 数组中的每一个子数组，对于子数组中的每个元素，检查该元素是否存在于 arr 中（即在 mapping 中有对应的索引），并且该元素的位置是否正确（即连续）。如果任一检查失败，立即返回 false。如果所有的元素都正确处理，最后检查 vis 是否等于 2^n-1（其中 n 是 arr 的长度），这表示 arr 中的所有元素都被覆盖了一次且仅一次。

时间复杂度: O(n)

空间复杂度: O(n)

# 添加详细注释的题解代码

class Solution:
    def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
        mapping = {} # 存储 arr 中每个值对应的索引
        n = len(arr) # arr 的长度
        for i in range(n): # 建立 arr 值到索引的映射
            mapping[arr[i]] = i
        vis = 0 # 位掩码，用于跟踪访问过的元素
        for piece in pieces: # 遍历每一个子数组
            pre = None # 前一个访问的元素的索引
            for p in piece: # 遍历子数组中的每一个元素
                if (p not in mapping) or (pre != None and pre+1 != mapping[p]): # 检查元素是否在 arr 中，且位置是否正确
                    return False
                if(vis & (1 << mapping[p]) == 1): # 检查该位置的元素是否已经被访问过
                    return False
                pre = mapping[p] # 更新前一个元素的索引
                vis |= (1 << mapping[p]) # 标记当前元素已访问
        return vis == 2**n-1 # 检查是否所有元素正好访问了一次

Explore

在算法中，每个来自pieces子数组的元素都会在映射mapping中查找。如果某个元素不存在于mapping中，即该元素不在arr数组中，算法会立即返回false。这确保了所有pieces中的元素都必须存在于arr中，否则无法形成arr数组。

使用位掩码vis来跟踪访问情况的优势在于空间效率和操作速度。位操作通常比其他数据结构（如哈希表或数组）更快，且消耗更少的空间。然而，位掩码的劣势是它的可扩展性较差，对于非常大的数据集或超出整数位数的情况不适用，且调试和理解上可能比较复杂。

在检查pieces中的元素顺序时，`pre+1 != mapping[p]`用于确保当前元素p在arr中的位置是紧接着前一个元素的位置。这是因为pieces数组中的子数组需要在arr中完全按照给定的顺序和连续位置出现。如果不满足这一条件，则说明pieces中的子数组无法按照顺序连续地匹配arr中的元素，因此返回false。

代码中的条件`vis & (1 << mapping[p]) == 1`存在逻辑错误。正确的检查方式应为`(vis & (1 << mapping[p])) != 0`，用于判断该位是否已经被设置。原表达式由于优先级问题，实际上先进行了`1 << mapping[p]`的移位操作，然后与vis进行与操作，最后判断结果是否等于1，这通常不会得到预期的结果。