我们先来看题目描述给你一个下标从 开始的二维整数数组 pairs其中 pairs[i] [starti, endi]。如果 pairs 的一个重新排列满足对每一个下标 i1 i pairs.length都有 endi-1 starti那么我们就认为这个重新排列是 pairs 的一个合法重新排列。 请你返回任意一个 pairs 的合法重新排列。 注意数据保证至少存在一个 pairs 的合法重新排列。1 pairs.length 1050 starti, endi 109读者可能会尝试把每个 pair 看作一个点并在所有 end 和 start 相等的 pair 之间连一条有向边。然而设 pair 的数量有 个这样构建的图将有 条边考虑 个 pair 满足 end 1另外 个 pair 满足 start 1 的数据无法满足本题的数据范围。并且读者还需要在这样构建的图中找出一条经过所有点恰好一次的路径即哈密顿路径^12这是一个 NP 完全问题同样无法满足本题的数据范围。上述建图的方式没有较好地利用 endi-1 starti 的性质。我们反过来将 start 和 end 看作点将每个 pair 看作从 start 指向 end 的有向边。这样建图自然保证了连续走过的两条边满足 endi-1 starti。更妙的是我们只需要找到一条经过所有边恰好一次的路径又回到了我们熟悉的有向图的欧拉路径问题。由于题目保证有解即保证存在欧拉路径我们可以省去大量判断直接使用 Hierholzer 算法即可。本题的 C 代码如下class Solution { public: vectorvectorint validArrangement(vectorvectorint pairs) { // 构建有向图 unordered_mapint, vectorint e; unordered_mapint, int inDeg, outDeg; for (auto p : pairs) { e[p[0]].push_back(p[1]); outDeg[p[0]]; inDeg[p[1]]; } int s -1; // 入度比出度少 1 的节点就是起点 for (auto p : e) if (inDeg[p.first] 1 outDeg[p.first]) s p.first; // 如果起点未指定说明存在欧拉回路选择任意一个非零度节点即可 if (s -1) s pairs[0][0]; vectorvectorint ans; functionvoid(int) dfs [](int sn) { while (e[sn].size() 0) { int fn e[sn].back(); // 删除有向边 sn - fn e[sn].pop_back(); // 继续遍历相邻点 dfs(fn); // 将有向边 sn - fn 加入结果序列中 ans.push_back({sn, fn}); } }; dfs(s); // ans 保存的是欧拉路径的倒序必须 reverse 才是正确答案 reverse(ans.begin(), ans.end()); return ans; } };