一、题目
给定一个长度为 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 。
子序列 是一个可以通过从另一个序列中删除一些元素或不删除任何元素，而不改变其余元素的顺序的序列。
二、示例
示例 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.length
- 1 <= n <= 104
- nums 是 [1, n] 范围内所有整数的排列
- 1 <= sequences.length <= 104
- 1 <= sequences[i].length <= 104
- 1 <= sum(sequences[i].length) <= 105
- 1 <= sequences[i][j] <= n
- sequences 的所有数组都是 唯一 的
- sequences[i] 是 nums 的一个子序列
三、解题思路
根据题意，我们可以将数字拼装为有向图，再根据拓扑排序来获得超序列。比如我们假设sequences = [[1,2],[1,3],[2,3]]，那么第一个数组[1, 2]，我们就可以构造node(1)和node(2)两个节点，然后由一条带箭头的线从node(1)指向node(2)。这样，node(1)当前的“入度”为0，node(2)的“入度”为1。其他的数组元素以此类推。那么我们可以看出，入度为0的节点就是整个排序后的头节点，然后是入度为1的节点，再然后就是入度为2的节点，以此类推。我们可以根据入度的不同，来最终排列出一个超序列。下面我们以sequences = [[1,2],[1,3],[2,3]]为例，看看构造一个唯一的超序列的具体步骤，如下图所示：
上面我们了解了唯一超序列的构造过程，那么怎么去判断是不是唯一的超序列呢？其实还是根据入度来判断。现在我们以sequences = [[1,2],[1,3]]为例。在第一个数组[1, 2]中，node(1)的入度为0，node(2)的入度为1；在第二个数组[1, 3]中，node(1)的入度依然为0，node(3)的入度为1。这时候我们发现，node(2)和node(3)的入度都是0了。那其实就可以得出一个结论：最短超序列第一个元素一定是node(1)，而第二个元素可能是node(2)，也可能是node(3)。那么就不满足最短超序列的唯一性了。下面我们以sequences = [[1,2],[1,3]]为例，看看构造一个不唯一的超序列的具体步骤，如下图所示：
那在实现上我们怎么去做的。我们发现，在整个过程中，要频率很高的去确定每个节点的入度数值，并且每个节点的value值其实是1 <= n <= 104，所以我们可以通过数组结构去存储每个节点的入度值——下标index代表节点值，具体值Array[index]代表节点的入度数。具体如下图所示：
元素节点元素，我们其实只关心两部分内容：节点value值和它所指向的子节点集合，由于其中需要排重（即：[1, 2]和[1, 2, 3]中，1指向的节点就是2，而不是2和2），所以我们采用Set数据结构去存储指向的子节点。如果发现Set中已经存在该子节点了，那么该子节点的入度数就不变化了，否则，会执行加1操作。节点元素结构如下所示：
关于拓扑排序，我们可以采用队列的方式进行实现。也就是说，当我们将sequences中的元素转换为有向图之后，那么首先将入度为0的元素放到队列中，此时判断该队列容纳的元素是不是大于1个，如果是，那么就表明最终会获得多个最短超序列，方法返回false。如果队列中容纳的元素个数是1个，那么就符合唯一最短超序列。记得每次循环结束后，都会将入度为0的子节点的入度数减一，并且将入度0的元素放入到队列中。并且在每次循环同事都要调用列队的poll方法将这个入度0的元素“踢出”队列，为下轮入列元素做准备。下面我们以sequences = [[1,2],[1,3]]为例，演示一下如何使用队列实现拓扑排序的：
四、代码实现
class Solution {
public boolean sequenceReconstruction(int[] nums, int[][] sequences) {
int[] inRef = new int[nums.length + 1]; // 记录【入度】次数
Set<Integer>[] ref = new HashSet[nums.length + 1]; // 用于记录每个元素与其【出度】元素的映射关系
/** 步骤1：计算每个元素的【入度】值，并且维护有关联的两个节点之间的连接 */
for (int[] sequence : sequences) {
for (int i = 1; i < sequence.length; i++) { // 第一个元素（index=0）没有【入度】，所以从index=1开始循环遍历
if (ref[sequence[i - 1]] == null) {
ref[sequence[i - 1]] = new HashSet();
}
// 返回true，表示set中没有此元素，那么可以增加该元素的【入度值】
if (ref[sequence[i - 1]].add(sequence[i])) {
inRef[sequence[i]] += 1; // "入度"值+1
}
}
}
/** 步骤2：初始化【入度为0】的队列 */
Queue<Integer> zeroInRefQueue = new ArrayDeque();
for (int i = 1; i < ref.length; i++) {
if (inRef[i] == 0) { // 只将【入度值】为0的放入队列中
zeroInRefQueue.add(i);
}
}
if (zeroInRefQueue.isEmpty()) { // 发生了互相引用，即：A——>B, B——>A
return false;
}
/** 步骤3：顺着节点引用路径查看是否有多条路径存在的情况 */
int index = 0;
while(!zeroInRefQueue.isEmpty()) {
int i = zeroInRefQueue.peek();
if (zeroInRefQueue.size() > 1 || nums[index] != i) { // 如果【入度值】为0的元素不再唯一，则说明超序列不唯一
return false;
}
zeroInRefQueue.poll();
if (ref[i] != null && !ref[i].isEmpty()) {
for (Integer num : ref[i]) {
inRef[num] -= 1;
if (inRef[num] == 0) {
zeroInRefQueue.add(num);
}
}
}
index++;
}
return true;
}
}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞&分享。
更多技术干货，欢迎大家关注公众号“爪哇缪斯”(o)/~ 「干货分享，每周更新」
