【2022-09-22每日一题】1640. 能否连接形成数组[Easy]

2022-09-22每日一题：1640. 能否连接形成数组

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

方法一：哈希表

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func canFormArray(arr []int, pieces [][]int) bool {
    // 哈希表构造比较巧妙
    ht := make(map[int]int, len(pieces))
    for i, p := range pieces {
        ht[p[0]] = i
    }
    for i := 0; i < len(arr); {
        j, ok := ht[arr[i]]
        if !ok {
            return false
        }
        for _, num := range pieces[j] {
            if arr[i] != num {
                return false
            }
            i++
        }
    }
    return true
}

rust

impl Solution {
    pub fn can_form_array(arr: Vec<i32>, pieces: Vec<Vec<i32>>) -> bool {
        let mut cache = vec![-1; 101];
        arr.iter().enumerate().for_each(|(i, v)| cache[*v as usize] = i as i32);
        for piece in pieces {
            let mut next = cache[piece[0] as usize];
            for p in piece {
                if cache[p as usize] == -1 || cache[p as usize] != next { return false; }
                next = cache[p as usize] + 1;
            }
        }
        true
    }
}

复杂度分析

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

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

排序 + 二分( 执行超时，非最优解法，只为开拓视野)

func canFormArray(arr []int, pieces [][]int) bool {
    n, m := len(arr), len(pieces)
    sort.Slice(pieces, func(i, j int) bool {
        return pieces[i][0] < pieces[j][0]
    })
    for i := 0; i < n; {
        l, r := 0, m - 1
        for l < r {
            // 为啥要加1呢
            mid := (l + r + 1) >> 1
            if pieces[mid][0] <= arr[i] {
                l = mid
            } else {
                r = mid - 1
            }
        }
        ln, idx := len(pieces[r]), 0
        for ; idx < ln && pieces[r][idx] == arr[i+idx]; idx++ {}
        if idx != ln {
            return false
        }
        i += ln
    }
    return true
}

复杂度分析

• 时间复杂度：排序复杂度为 O(mlogm)；构造的复杂度为 O(nlogm)。整体复杂度为 O(mlogm+nlogm)
• 空间复杂度：O(logm)

LeetCode题库地址

• https://leetcode.cn/problems/check-array-formation-through-concatenation