题目描述
给你一个下标从 0 开始的二维整数数组 pairs
,其中 pairs[i] = [start_i, end_i]
。如果 pairs
的一个重新排列,满足对每一个下标 i
(1 <= i < pairs.length
)都有 end_{i-1} == start_{i}
,那么我们就认为这个重新排列是 pairs
的一个 合法重新排列。
请你返回 任意一个 pairs
的合法重新排列。
注意:数据保证至少存在一个 pairs
的合法重新排列。
样例
输入:pairs = [[5,1],[4,5],[11,9],[9,4]]
输出:[[11,9],[9,4],[4,5],[5,1]]
解释:
输出的是一个合法重新排列,因为每一个 end_{i-1} 都等于 start_{i}。
end0 = 9 == 9 = start1
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3
输入:pairs = [[1,3],[3,2],[2,1]]
输出:[[1,3],[3,2],[2,1]]
解释:
输出的是一个合法重新排列,因为每一个 end_{i-1} 都等于 start_{i}。
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]]
解释:
输出的是一个合法重新排列,因为每一个 end_{i-1} 都等于 start_{i}。
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2
限制
- 1
<= pairs.length <= 10^5
pairs[i].length == 2
0 <= start_i, end_i <= 10^9
start_i != end_i
pairs
中不存在一模一样的数对。- 至少 存在 一个合法的
pairs
重新排列。
算法
(有向图的欧拉路径) $O(n)$
- 对每个数对 $e_i = (x, y)$,构造一条有向边 $x \to y$,属性为 $i$。
- 求整个有向图的欧拉路径,输入路径上的属性组成答案。
- 求欧拉路径可以使用
Fleury 算法
,从起点开始深度优先遍历整个图,最后记录当前点作为路径,然后反向输出路径。 - 如果所有点的入度等于出度,则任意点都可以当做起点。否则,需要从出度减入度等于 1 的点开始遍历。
时间复杂度
- 遍历所有点和边一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储图,递归的系统栈,以及欧拉路相关的数据结构。
C++ 代码
const int N = 200010;
class Solution {
private:
vector<pair<int, int>> graph[N];
int deg[N];
vector<int> path;
void dfs(int u, int prev) {
while (!graph[u].empty()) {
int v = graph[u].back().first, e = graph[u].back().second;
graph[u].pop_back();
dfs(v, e);
}
if (prev != -1)
path.push_back(prev);
}
public:
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
const int n = pairs.size();
vector<int> nums;
for (int i = 0; i < n; i++) {
int x = pairs[i][0], y = pairs[i][1];
nums.push_back(x);
nums.push_back(y);
}
sort(nums.begin(), nums.end());
const int m = unique(nums.begin(), nums.end()) - nums.begin();
nums.resize(m);
for (int i = 0; i < m; i++)
deg[i] = 0;
for (int i = 0; i < n; i++) {
int x = pairs[i][0], y = pairs[i][1];
x = lower_bound(nums.begin(), nums.end(), x) - nums.begin();
y = lower_bound(nums.begin(), nums.end(), y) - nums.begin();
graph[x].emplace_back(y, i);
deg[x]++; deg[y]--;
}
int first = 0;
for (int i = 0; i < m; i++)
if (deg[i] == 1) {
first = i;
break;
}
dfs(first, -1);
vector<vector<int>> ans;
for (int i = n - 1; i >= 0; i--)
ans.push_back({pairs[path[i]][0], pairs[path[i]][1]});
return ans;
}
};