likes
comments
collection
share

【C/C++】剑指 Offer II 115. 重建序列

作者站长头像
站长
· 阅读数 86

题目链接：剑指 Offer II 115. 重建序列

题目描述

给定一个长度为 n 的整数数组 nums ，其中 nums 是范围为 [1，n] 的整数的排列。还提供了一个 2D 整数数组 sequences ，其中 sequences[i] 是 nums 的子序列。 检查 nums 是否是唯一的最短 超序列 。最短 超序列 是 长度最短 的序列，并且所有序列 sequences[i] 都是它的子序列。对于给定的数组 sequences ，可能存在多个有效的 超序列 。

  • 例如，对于 sequences = [[1,2],[1,3]] ，有两个最短的 超序列 ，[1,2,3] 和 [1,3,2] 。
  • 而对于 sequences = [[1,2],[1,3],[1,2,3]] ，唯一可能的最短 超序列 是 [1,2,3] 。[1,2,3,4] 是可能的超序列，但不是最短的。

如果 nums 是序列的唯一最短 超序列 ，则返回 true ，否则返回 false 。 子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。

提示:

  • n==nums.lengthn == nums.lengthn==nums.length
  • 1⩽n⩽1041 \leqslant n \leqslant 10^41⩽n⩽104
  • nums 是 [1, n] 范围内所有整数的排列
  • 1⩽sequences.length⩽1041 \leqslant sequences.length \leqslant 10^41⩽sequences.length⩽104
  • 1⩽sequences[i].length⩽1041 \leqslant sequences[i].length \leqslant 10^41⩽sequences[i].length⩽104
  • 1⩽sum(sequences[i].length)⩽1051 \leqslant sum(sequences[i].length) \leqslant 10^51⩽sum(sequences[i].length)⩽105
  • 1⩽sequences[i][j]⩽n1 \leqslant sequences[i][j] \leqslant n1⩽sequences[i][j]⩽n
  • sequences 的所有数组都是 唯一 的
  • sequences[i] 是 nums 的一个子序列

示例 1：

输入：nums = [1,2,3], sequences = [[1,2],[1,3]]
输出：false
解释：有两种可能的超序列：[1,2,3]和[1,3,2]。
序列 [1,2] 是[1,2,3]和[1,3,2]的子序列。
序列 [1,3] 是[1,2,3]和[1,3,2]的子序列。
因为 nums 不是唯一最短的超序列，所以返回false。

示例 2：

输入：nums = [1,2,3], sequences = [[1,2]]
输出：false
解释：最短可能的超序列为 [1,2]。
序列 [1,2] 是它的子序列：[1,2]。
因为 nums 不是最短的超序列，所以返回false。

示例 3：

输入：nums = [1,2,3], sequences = [[1,2],[1,3],[2,3]]
输出：true
解释：最短可能的超序列为[1,2,3]。
序列 [1,2] 是它的一个子序列：[1,2,3]。
序列 [1,3] 是它的一个子序列：[1,2,3]。
序列 [2,3] 是它的一个子序列：[1,2,3]。
因为 nums 是唯一最短的超序列，所以返回true。

整理题意

题目给定一个长度为 n 的数组 nums，其中包含了 1 到 n 的所有整数的排列，另外还给了一些 nums 的子序列数组 sequences。

判断 nums 是否是这些子序列数组 sequences 唯一且最短的序列。因为对于给定的子序列数组 sequences ，可能存在多个有效的序列。

解题思路分析

该题的核心在于判断子序列数组 sequences 是否能够构造出唯一的 1 到 n 的所有整数的排列，如果能，那么一定是最短的序列。

首先可以将给定的子序列数组 sequences 看做每个整数在不同情况下的排名，根据这个排名判断是否能够构造出唯一的整数排名。

根据每个子序列构造一个有向图，数字 1 到 n 分别表示图中的 n 个结点，每个序列中的相邻数字表示的结点之间存在一条有向边（1 -> 2 表示 1 的排名大于 2）。根据给定的序列构造超序列等价于有向图的拓扑排序。

拓扑排序就是不断将有向图中入度为 0 的节点删除，在删除节点时同时维护该节点所连节点的入度。最后得到的排序就是拓扑排序。

在拓扑排序的过程中，如果同时有两个以上的节点入度为零，则表示当前排名的数字有多种可能，因此子序列数组 sequences 所构造出来的序列也并非唯一的，所以 nums 并非那个唯一最短的序列，直接返回 false。

为什么拓扑排序结束，就能表示 nums 是唯一的最短超序列？

因为只有当 1 到 n 中的所有数字都在至少一个序列中出现时，才可能执行完整的拓扑排序。（题目给定的数据提示：nums 是 [1, n] 范围内所有整数的排列）

  • 首先由于 sequences 中的每个序列都是 nums 的子序列，因此序列中不存在环，这些数字中一定存在入度为 0 的数字。
  • 其次如果一个数字没有在任何序列中出现，则最开始就会有两个以上的数字入度为 0，那么排列的第一个数字就不唯一，此时直接返回 false。因此如果执行完整的拓扑排序，则 1 到 n 中的所有数字都在至少一个序列中出现。

因为当执行完整的拓扑排序时，得到的超序列的长度为 n。

  • 根据上述条件进行拓扑排序，在最后会得到 1 到 n 中的所有数字的排列，所以得到的超序列的长度为 n。

综上，当拓扑排序结束时，就能表示 nums 是唯一的最短超序列

  • 因为 sequences 中的序列都是 nums 的子序列，那么当 sequences 能够构造出唯一的 1 到 n 中的所有数字的排列，就表示这个构造的序列一定等于 nums。

具体实现

  1. 使用数组记录每个节点的入度，在建图时维护每个节点的入度。
  2. 对 1 到 n 中的所有数字进行拓扑排序，不断取出入度为零的节点，删除该节点所连接的边，同时维护边所连接的节点的入度，当入度为 0 时放入拓扑排序的队列中。
  3. 当拓扑排序的队列中元素个数有 2 个以上时，表示下一个排列不唯一，此时直接返回 false。
  4. 当拓扑排序完成时，表示 1 到 n 中的所有整数排列唯一，也就表示 nums 唯一，此时返回 true。

复杂度分析

  • 时间复杂度：O(n+m)O(n + m)O(n+m)，其中 n 是数组 nums 的长度，m 是 sequences 中的所有序列长度之和。建图和拓扑排序都需要 O(n+m)O(n + m)O(n+m) 的时间。
  • 空间复杂度：O(n+m)O(n + m)O(n+m)，其中 n 是数组 nums 的长度，m 是 sequences 中的所有序列长度之和。需要 O(n+m)O(n + m)O(n+m) 的空间存储图信息，需要 O(n)O(n)O(n) 的空间存储每个结点的入度，拓扑排序过程中队列空间是 O(n)O(n)O(n)。

代码实现

class Solution {
public:
    bool sequenceReconstruction(vector<int>& nums, vector<vector<int>>& sequences) {
        int n = nums.size();
        //indegrees[i] 记录节点i的入度
        int indegrees[n + 1];
        memset(indegrees, 0, sizeof(indegrees));
        //根据 sequence 建有向图
        vector<vector<int>> G(n + 1);
        for(int i = 0; i <= n; i++) G[i].clear();
        int m = sequences.size();
        for(vector<int> &sequence : sequences){
            int k = sequence.size();
            for(int i = 1; i < k; i++){
                int pre = sequence[i - 1], nxt = sequence[i];
                G[pre].emplace_back(nxt);
                //记录入度
                indegrees[nxt]++;
            }
        }
        //拓扑排序
        queue<int> que;
        while(que.size()) que.pop();
        for(int i = 1; i <= n; i++) if(!indegrees[i]) que.push(i);
        while(que.size()){
            //如果队列中有两个以上的入度为零的点表示拓扑排序不唯一返回false
            if(que.size() > 1) return false;
            int now = que.front(); que.pop();
            for(int nxt : G[now]){
                indegrees[nxt]--;
                if(!indegrees[nxt]) que.push(nxt);
            }
        }
        //成功拓扑排序返回true表示nums是唯一最短超序列
        return true;
    }
};

总结

  • vector 的 emplace_back() 操作代替 push_back() 操作可以优化时间和空间。emplace_back() 函数的作用是减少对象拷贝和构造次数，是 C++11 中的新特性,在效率上相比较于 push_back() 有了一定的提升，包括在内存优化方面和运行效率方面。内存优化主要体现在使用了就地构造（直接在容器内构造对象，不用拷贝一个复制品再使用）强制类型转换的方法来实现，在运行效率方面，由于省去了拷贝构造过程，因此也有一定的提升。
  • 该题的核心在于考虑 sequences 是否能够构造出唯一的 1 到 n 的所有整数的排列。由于sequences 中的序列都是 nums 的子序列，所以当 sequences 能够构造出唯一的 1 到 n 的所有整数的排列，也就表示该构造出来的排列一定等于 nums。
  • 由于该题是确定排列顺序，可以使用 拓扑排序 来完成，难点在于如何将该题转化为拓扑排序问题。
  • 题目数据限制要求较多，需要注意题目的数据提示，避免考虑多余情况。比如 nums 是 [1, n] 范围内所有整数的排列。
  • 测试结果：

【C/C++】剑指 Offer II 115. 重建序列

结束语

人生最好的一天，永远是今天；最好的一刻，永远是此刻。日月既往，不可复追。过往无论沮丧或是遗憾，都已成为过往。在以后的日子里，请保持你的热情和努力，勇往直前。新的一天，加油！

转载自:https://juejin.cn/post/7149019717523472397
评论
请登录