class Solution {
public:
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
}
};
2097. 合法重新排列数对
给你一个下标从 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 <= 105pairs[i].length == 20 <= starti, endi <= 109starti != endipairs 中不存在一模一样的数对。pairs 重新排列。原站题解
golang 解法, 执行用时: 512 ms, 内存消耗: 67.6 MB, 提交时间: 2023-10-27 22:19:37
func validArrangement(pairs [][]int) [][]int {
g := map[int][]int{}
inDeg := map[int]int{}
for _, p := range pairs {
v, w := p[0], p[1]
g[v] = append(g[v], w) // 建图（有向图）
inDeg[w]++ // 统计入度
}
start := 0
for i, es := range g {
if len(es) == inDeg[i]+1 { // 半欧拉图：存在出度比入度大 1 的点，那就把它当成起点
start = i
break
}
start = i // 欧拉图：随便找一个点当起点
}
m := len(pairs)
ans := make([][]int, 0, m)
var dfs func(int)
dfs = func(v int) {
for len(g[v]) > 0 {
w := g[v][0]
g[v] = g[v][1:]
dfs(w)
ans = append(ans, []int{v, w}) // 记录欧拉路径
}
}
dfs(start)
for i := 0; i < m/2; i++ {
ans[i], ans[m-1-i] = ans[m-1-i], ans[i]
}
return ans
}
cpp 解法, 执行用时: 1124 ms, 内存消耗: 306.7 MB, 提交时间: 2023-10-27 22:19:20
class Solution {
public:
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
// 存储图
unordered_map<int, vector<int>> edges;
// 存储入度和出度
unordered_map<int, int> indeg, outdeg;
for (const auto& p: pairs) {
int x = p[0], y = p[1];
edges[x].push_back(y);
++indeg[y];
++outdeg[x];
}
// 寻找起始节点
int start = pairs[0][0];
for (const auto& [x, occ]: outdeg) {
// 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点
if (occ == indeg[x] + 1) {
start = x;
break;
}
}
vector<vector<int>> ans;
// 深度优先搜索（Hierholzer 算法）求解欧拉通路
function<void(int)> dfs = [&](int u) {
while (!edges[u].empty()) {
int v = edges[u].back();
edges[u].pop_back();
dfs(v);
ans.push_back({u, v});
}
};
dfs(start);
reverse(ans.begin(), ans.end());
return ans;
}
};
python3 解法, 执行用时: 732 ms, 内存消耗: 170.8 MB, 提交时间: 2023-10-27 22:18:51
class Solution:
def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
# 存储图
edges = defaultdict(list)
# 存储入度和出度
indeg, outdeg = Counter(), Counter()
for x, y in pairs:
edges[x].append(y)
indeg[y] += 1
outdeg[x] += 1
# 寻找起始节点
start = pairs[0][0]
for x in outdeg:
# 如果有节点出度比入度恰好多 1，那么只有它才能是起始节点
if outdeg[x] == indeg[x] + 1:
start = x
break
ans = list()
# 深度优先搜索（Hierholzer 算法）求解欧拉通路
def dfs(u: int) -> None:
while edges[u]:
v = edges[u].pop()
dfs(v)
ans.append([u, v])
dfs(start)
return ans[::-1]
python3 解法, 执行用时: 572 ms, 内存消耗: 170 MB, 提交时间: 2023-10-27 22:18:33
class Solution:
def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
nes = defaultdict(list)
cnt = defaultdict(int)
for u, v in pairs:
nes[u].append(v)
cnt[u] += 1
cnt[v] -= 1
st = pairs[0][0]
for node, c in cnt.items():
if c == 1:
st = node
break
pts = []
def dfs(node):
v = nes[node]
while len(v):
dfs(v.pop())
pts.append(node)
dfs(st)
return [[pts[i], pts[i-1]] for i in range(len(pts) - 1, 0, -1)]
cpp 解法, 执行用时: 656 ms, 内存消耗: 259.3 MB, 提交时间: 2023-10-27 22:18:05
class Solution {
public:
vector<int> res;
void dfs(int node, unordered_map<int, vector<int>>& nes) {
auto& v = nes[node];
while(v.size()) {
auto ne = v.back();
v.pop_back();
dfs(ne, nes);
}
res.push_back(node);
}
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
unordered_map<int, vector<int>> nes;
unordered_map<int, int> incnt;
for(auto& p : pairs) {
nes[p[0]].emplace_back(p[1]);
incnt[p[1]]++;
}
int start = -1;
for(const auto & p : nes) {
int node = p.first;
if(p.second.size() == incnt[node] + 1) {
start = node;
}
}
if(start == -1) {
start = pairs[0][0];
}
dfs(start, nes);
reverse(res.begin(), res.end());
vector<vector<int>> ret;
for(int i = 1; i < res.size(); ++i) {
ret.push_back({res[i-1], res[i]});
}
return ret;
}
};
cpp 解法, 执行用时: 1084 ms, 内存消耗: 302.1 MB, 提交时间: 2023-10-27 22:17:45
class Solution {
map<int, vector<int>> mp;
map<int, int> deg;
vector<vector<int>> ans;
void dfs(int sn) {
vector<int> &e = mp[sn];
while (!e.empty()) {
int fn = e.back();
e.pop_back();
dfs(fn);
ans.push_back(vector<int>{sn, fn});
}
}
public:
vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
// 建图
for (auto &pair : pairs) {
mp[pair[0]].push_back(pair[1]);
deg[pair[0]]--; deg[pair[1]]++;
}
// 检查度数
for (auto it = deg.begin(); it != deg.end(); it++) if (it->second == -1) dfs(it->first);
if (ans.empty()) dfs(deg.begin()->first);
reverse(ans.begin(), ans.end());
return ans;
}
};