文章目录
1. 题目
2. 解题
1. 题目
给你一个下标从 0 开始的二维整数数组 pairs ，其中 pairs[i] = [starti, endi] 。如果 pairs 的一个重新排列，满足对每一个下标 i （ 1 <= i < pairs.length ）都有 endi-1 == starti ，那么我们就认为这个重新排列是 pairs 的一个 合法重新排列 。
请你返回 任意一个 pairs 的合法重新排列。
注意：数据保证至少存在一个 pairs 的合法重新排列。
示例 1： 输入：pairs = [[5,1],[4,5],[11,9],[9,4]] 输出：[[11,9],[9,4],[4,5],[5,1]] 解释： 输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。 end0 = 9 == 9 = start1 end1 = 4 == 4 = start2 end2 = 5 == 5 = start3 示例 2： 输入：pairs = [[1,3],[3,2],[2,1]] 输出：[[1,3],[3,2],[2,1]] 解释： 输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。 end0 = 3 == 3 = start1 end1 = 2 == 2 = start2 重新排列后的数组 [[2,1],[1,3],[3,2]] 和 [[3,2],[2,1],[1,3]] 都是合法的。 示例 3： 输入：pairs = [[1,2],[1,3],[2,1]] 输出：[[1,2],[2,1],[1,3]] 解释： 输出的是一个合法重新排列，因为每一个 endi-1 都等于 starti 。 end0 = 2 == 2 = start1 end1 = 1 == 1 = start2 提示： 1 <= pairs.length <= 10^5 pairs[i].length == 2 0 <= starti, endi <= 10^9 starti != endi pairs 中不存在一模一样的数对。 至少 存在 一个合法的 pairs 重新排列。
2. 解题
类似题目：LeetCode 332. 重新安排行程（欧拉路径）
欧拉回路的充要条件
无向图：所有点的度数都为偶数
有向图：所有点的入度==出度
欧拉路径的充要条件
无向图：除两点(起点与终点)外其余点的度数都为偶数
有向图：除两点(起点 入度+1=出度，终点 入度−1=出度)外，其余点的 入度==出度
将 pair [A, B] 看做是点 A 到 B 的一条有向边
记录出入度，建图
然后从满足上面条件的点（起点 入度+1=出度）开始 dfs
class Solution { vector<int> path; public: vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { int n = pairs.size(); unordered_map<int, multiset<int>> g; //图 unordered_map<int, int> indegree, outdegree; for(int i = 0; i < n; ++i) { int x = pairs[i][0], y = pairs[i][1]; outdegree[x]++; indegree[y]++; g[x].insert(y); } int start = pairs[0][0]; for(int i = 0; i < n; ++i) { int x = pairs[i][0], y = pairs[i][1]; int indegree_i = indegree.count(x) ? indegree[x] : 0; int outdegree_i = outdegree.count(x) ? outdegree[x] : 0; if(indegree_i + 1 == outdegree_i) { start = x; break; } } dfs(start, g); vector<vector<int>> ans; for(int i = path.size()-1; i > 0; i--) // 逆序输出就是欧拉路径 ans.push_back({path[i], path[i-1]}); return ans; } void dfs(int idx, unordered_map<int, multiset<int>>& g) { while(g[idx].size()) { int nt = *g[idx].begin(); g[idx].erase(g[idx].begin()); dfs(nt, g); } path.push_back(idx); } };
952 ms 302.7 MB C++
