2024-01-10：用 go 语言，给你一个下标从 0 开始的二维整数数组 pairs

其中 pairs[i] = [starti, endi]

如果 pairs 的一个重新排列

满足对每一个下标 i （ 1 <= i < pairs.length ）

都有 endi-1 == starti ，

那么我们就认为这个重新排列是 pairs 的一个 合法重新排列。

请你返回 任意一个 pairs 的合法重新排列。

注意：数据保证至少存在一个 pairs 的合法重新排列。

输入：pairs = [[5,1],[4,5],[11,9],[9,4]]。

输出：[[11,9],[9,4],[4,5],[5,1]]。

来自 lc 的 2097 题，合法重新排列数对。

答案 2024-01-06：

来自左程云。

灵捷3.5

大体步骤如下：

1.创建图和度数字典：遍历输入的 pairs 数组，通过创建一个空的图和一个空的度数字典。将 pairs 中的每个元素的起点和终点作为图的键，值初始化为空切片，同时将起点和终点作为度数字典的键，并将对应的值初始化为 0。

2.构建图和计算度数：再次遍历 pairs 数组，将每个元素的起点作为图的键，在对应的值中添加终点，并将起点的度数加 1。同时，将每个元素的终点作为图的键，在对应的值中添加起点，并将终点的度数减 1。

3.确定起点：通过遍历度数字典，找到度数为 1 的点作为起点，将其保存在变量 from 中。

4.深度优先搜索：定义一个递归的深度优先搜索函数 dfs，接收当前节点 from、图和记录路径的二维切片 record 作为参数。在该函数中，首先获取 from 节点的相邻节点 next，并将当前节点 from 添加到 record 中。然后遍历 next 中的每个节点 to，调用 dfs 函数递归地搜索 to 节点，并将 from 和 to 形成的边添加到 record 中。

5.执行深度优先搜索：调用 dfs 函数，将起点 from、图和空的 record 作为参数。

6.反转路径：根据 record 中的记录路径，将路径反转得到最终的合法重新排列。

7.返回结果：将反转后的路径作为结果返回。

总的时间复杂度为 O(n)，其中 n 为 pairs 数组的长度。构建图和计算度数的过程需要遍历两次 pairs 数组，时间复杂度为 O(n)。深度优先搜索的时间复杂度为 O(n)，主要取决于图的节点数量。反转路径的过程需要遍历 record 数组，时间复杂度为 O(n)。

总的额外空间复杂度为 O(n)，主要是用来存储图和路径记录的空间。

go 完整代码如下：

package main
import (  "fmt")
func validArrangement(pairs [][]int) [][]int {  graph := make(map[int][]int)  degrees := make(map[int]int)  for _, pair := range pairs {    graph[pair[0]] = []int{}    graph[pair[1]] = []int{}    degrees[pair[0]] = 0    degrees[pair[1]] = 0  }  for _, pair := range pairs {    graph[pair[0]] = append(graph[pair[0]], pair[1])    degrees[pair[0]]++    degrees[pair[1]]--  }  from := pairs[0][0]  for cur, degree := range degrees {    if degree == 1 {      from = cur      break    }  }  record := [][]int{}  dfs(from, graph, &record)  n := len(record)  ans := make([][]int, n)  for i, j := n-1, 0; j < n; i, j = i-1, j+1 {    ans[i] = record[j]  }  return ans}
func dfs(from int, graph map[int][]int, record *[][]int) {  next := graph[from]  for len(next) > 0 {    to := next[0]    next = next[1:]    dfs(to, graph, record)    *record = append(*record, []int{from, to})  }}
func main() {  pairs := [][]int{{5, 1}, {4, 5}, {11, 9}, {9, 4}}  result := validArrangement(pairs)  fmt.Println(result)}