LeetCode 1640. 能否连接形成数组

墨蓝 2022-12-19 13:14 149阅读 0赞

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

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

使用unordered\_map查找起来比较方便，并且查找速度最快能到O（1），与哈希函数的质量有关，最差查找情况速度为O（n)：

class Solution { 
    public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) { 
            unordered_map<int, vector<int>*> m;    // 存放以子数组中第一个元素为键，指向子数组的指针为值的map
            for (vector<int>& sub : pieces) { 
                m[sub[0]] = ⊂
            }
    
            for (int i = 0; i < arr.size(); ++i) { 
                auto it = m.find(arr[i]);
                if (it == m.end()) {     // 如果数组数组中没有符合条件的子数组
                    cout << "it == m.end() and now i = " << i << endl;
                    return false;
                }
    
                for (int iInPieces : *(it->second)) { 
                    cout << iInPieces << endl;
                    if (iInPieces != arr[i]) {     // 如果子数组中的数字不符合条件
                        cout << iInPieces << " != " << arr[i] << endl;
                        return false;
                    }
                    ++i;
                }
                --i;    // 由于循环的最后i会自增，所以最后相当于i自增了两次
            }
    
            return true;
        }
    };