1640-能否连接形成数组

Raphael Liu Lv10

给你一个整数数组 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 固定 pieces 的放置。使用哈希表 index 记录 pieces 各个数组的首元素与数组下标的对应关系。

我们不断地将 pieces 中的数组与数组 arr 相对应,对于当前遍历的元素 arr}[i],如果它不存在于哈希表中,说明我们无法将 pieces 与数组 arr 相对应,直接返回 false;否则我们找到对应的数组 pieces}[j],然后将它与 arr}[i] 及之后的整数进行比较(在比较过程中,如果判断相等不成立,直接返回 false),判断都相等后,将 i 相应地向后移。全部 pieces 都匹配成功后,返回 true。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def canFormArray(self, arr: List[int], pieces: List[List[int]]) -> bool:
index = {p[0]: i for i, p in enumerate(pieces)}
i = 0
while i < len(arr):
if arr[i] not in index:
return False
p = pieces[index[arr[i]]]
if arr[i: i + len(p)] != p:
return False
i += len(p)
return True
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
bool canFormArray(vector<int> &arr, vector<vector<int>> &pieces) {
unordered_map<int, int> index;
for (int i = 0; i < pieces.size(); i++) {
index[pieces[i][0]] = i;
}
for (int i = 0; i < arr.size();) {
auto it = index.find(arr[i]);
if (it == index.end()) {
return false;
}
for (int x : pieces[it->second]) {
if (arr[i++] != x) {
return false;
}
}
}
return true;
}
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public boolean canFormArray(int[] arr, int[][] pieces) {
int n = arr.length, m = pieces.length;
Map<Integer, Integer> index = new HashMap<Integer, Integer>();
for (int i = 0; i < m; i++) {
index.put(pieces[i][0], i);
}
for (int i = 0; i < n;) {
if (!index.containsKey(arr[i])) {
return false;
}
int j = index.get(arr[i]), len = pieces[j].length;
for (int k = 0; k < len; k++) {
if (arr[i + k] != pieces[j][k]) {
return false;
}
}
i = i + len;
}
return true;
}
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
public bool CanFormArray(int[] arr, int[][] pieces) {
int n = arr.Length, m = pieces.Length;
Dictionary<int, int> index = new Dictionary<int, int>();
for (int i = 0; i < m; i++) {
index.Add(pieces[i][0], i);
}
for (int i = 0; i < n;) {
if (!index.ContainsKey(arr[i])) {
return false;
}
int j = index[arr[i]], len = pieces[j].Length;
for (int k = 0; k < len; k++) {
if (arr[i + k] != pieces[j][k]) {
return false;
}
}
i = i + len;
}
return true;
}
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#define MAX(a, b) ((a) > (b) ? (a) : (b))

typedef struct {
int key;
int val;
UT_hash_handle hh;
} HashItem;

HashItem *hashFindItem(HashItem **obj, int key) {
HashItem *pEntry = NULL;
HASH_FIND_INT(*obj, &key, pEntry);
return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
if (hashFindItem(obj, key)) {
return false;
}
HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
pEntry->key = key;
pEntry->val = val;
HASH_ADD_INT(*obj, key, pEntry);
return true;
}

bool hashSetItem(HashItem **obj, int key, int val) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
hashAddItem(obj, key, val);
} else {
pEntry->val = val;
}
return true;
}

int hashGetItem(HashItem **obj, int key, int defaultVal) {
HashItem *pEntry = hashFindItem(obj, key);
if (!pEntry) {
return defaultVal;
}
return pEntry->val;
}

void hashFree(HashItem **obj) {
HashItem *curr = NULL, *tmp = NULL;
HASH_ITER(hh, *obj, curr, tmp) {
HASH_DEL(*obj, curr);
free(curr);
}
}

bool canFormArray(int* arr, int arrSize, int** pieces, int piecesSize, int* piecesColSize){
int n = arrSize, m = piecesSize;
HashItem *index = NULL;
for (int i = 0; i < m; i++) {
hashAddItem(&index, pieces[i][0], i);
}
for (int i = 0; i < n;) {
if (!hashFindItem(&index, arr[i])) {
hashFree(&index);
return false;
}
int j = hashGetItem(&index, arr[i], 0);
int len = piecesColSize[j];
for (int k = 0; k < len; k++) {
if (arr[i + k] != pieces[j][k]) {
hashFree(&index);
return false;
}
}
i = i + len;
}
hashFree(&index);
return true;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var canFormArray = function(arr, pieces) {
const n = arr.length, m = pieces.length;
const index = new Map();
for (let i = 0; i < m; i++) {
index.set(pieces[i][0], i);
}
for (let i = 0; i < n;) {
if (!index.has(arr[i])) {
return false;
}
const j = index.get(arr[i]), len = pieces[j].length;
for (let k = 0; k < len; k++) {
if (arr[i + k] != pieces[j][k]) {
return false;
}
}
i = i + len;
}
return true;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func canFormArray(arr []int, pieces [][]int) bool {
index := make(map[int]int, len(pieces))
for i, p := range pieces {
index[p[0]] = i
}
for i := 0; i < len(arr); {
j, ok := index[arr[i]]
if !ok {
return false
}
for _, x := range pieces[j] {
if arr[i] != x {
return false
}
i++
}
}
return true
}

复杂度分析

  • 时间复杂度:O(n),其中 n 是数组 arr 的长度。

  • 空间复杂度:O(n)。保存哈希表需要 O(n) 的空间。

 Comments
On this page
1640-能否连接形成数组