跳至主要內容

1640. 能否连接形成数组

1640. 能否连接形成数组

🟢   🔖  数组 哈希表  🔗 力扣open in new window LeetCodeopen in new window

题目

You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].

Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [15,88], pieces = [[88],[15]]

Output: true

Explanation: Concatenate [15] then [88]

Example 2:

Input: arr = [49,18,16], pieces = [[16,18,49]]

Output: false

Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 3:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]

Output: true

Explanation: Concatenate [91] then [4,64] then [78]

Constraints:

  • 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
  • The integers in arr are distinct.
  • The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

题目大意

给你一个整数数组 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 扁平化成一维数组，数组中的所有整数互不相同）

解题思路

题目要求判断数组 arr 是否可以通过串联 pieces 中的子数组（按原序列顺序）形成，因此每个子数组在 arr 中必须是相邻的。

  1. 建立索引映射：

    • 使用哈希表 numMap 将 arr 中的每个数字与其索引建立映射关系，方便快速查询某个数字的位置。

  2. 验证子数组顺序：

    • 遍历 pieces 中的每个子数组，验证其是否可以完全匹配 arr 中的某段连续子序列：
      • 如果子数组的首元素不在 arr 中，直接返回 false。
      • 对子数组的每两个相邻元素，如果它们在 arr 中不是连续出现（通过索引的差值判断），直接返回 false。

  3. 遍历结束后，如果所有子数组都满足上述条件，返回 true。

复杂度分析

  • 时间复杂度：O(n + m)

    • 建立映射：O(n)，其中 n 是 arr 的长度。
    • 验证子数组：O(m)，其中 m 是 pieces 中所有子数组元素的总数量。
    • 总体复杂度为 O(n + m)。

  • 空间复杂度：O(n)，使用 numMap 存储映射表。

代码

/**
 * @param {number[]} arr
 * @param {number[][]} pieces
 * @return {boolean}
 */
var canFormArray = function (arr, pieces) {
	// 创建 num -> index 的映射
	let numMap = new Map(arr.map((num, i) => [num, i]));

	for (let piece of pieces) {
		for (let i = 0; i < piece.length; i++) {
			// 检查子数组是否连续
			if (!numMap.has(piece[i])) return false;

			if (i > 0 && numMap.get(piece[i]) !== numMap.get(piece[i - 1]) + 1)
				return false;
		}
	}

	return true;
};
Copyright © 2024 2xiao