Hard

题目描述

给你一个下标从 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 排列

解题思路

这个问题可以转化为图论中的欧拉路径问题。

核心思路：

  1. 将每个数对 [start, end] 看作有向图的一条边，从节点 start 指向节点 end
  2. 问题转化为在这个有向图中找到一条欧拉路径，即遍历所有边恰好一次的路径
  3. 使用Hierholzer算法来找欧拉路径

算法步骤：

  1. 构建邻接表和计算每个节点的入度、出度
  2. 找到欧拉路径的起点：
    • 如果存在出度比入度多1的节点，它就是起点
    • 否则可以从任意有边的节点开始
  3. 使用DFS + 栈的方式实现Hierholzer算法：
    • 从起点开始DFS，每次选择一条未访问的边
    • 当无法继续时，将当前节点加入结果路径
    • 回溯到有未访问边的节点继续
  4. 最后将路径反转得到正确的欧拉路径

时间复杂度： O(V + E)，其中V是节点数，E是边数 空间复杂度： O(V + E)

代码实现

class Solution {
public:
    vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
        unordered_map<int, vector<int>> graph;
        unordered_map<int, int> inDegree, outDegree;
        
        // 构建图和计算度数
        for (auto& pair : pairs) {
            int start = pair[0], end = pair[1];
            graph[start].push_back(end);
            outDegree[start]++;
            inDegree[end]++;
        }
        
        // 找起点
        int startNode = pairs[0][0];
        for (auto& [node, out] : outDegree) {
            if (out - inDegree[node] == 1) {
                startNode = node;
                break;
            }
        }
        
        vector<int> path;
        stack<int> stk;
        stk.push(startNode);
        
        while (!stk.empty()) {
            int curr = stk.top();
            if (!graph[curr].empty()) {
                int next = graph[curr].back();
                graph[curr].pop_back();
                stk.push(next);
            } else {
                path.push_back(curr);
                stk.pop();
            }
        }
        
        vector<vector<int>> result;
        for (int i = path.size() - 1; i > 0; i--) {
            result.push_back({path[i], path[i-1]});
        }
        
        return result;
    }
};

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict, deque
        
        graph = defaultdict(deque)
        in_degree = defaultdict(int)
        out_degree = defaultdict(int)
        
        # 构建图和计算度数
        for start, end in pairs:
            graph[start].append(end)
            out_degree[start] += 1
            in_degree[end] += 1
        
        # 找起点
        start_node = pairs[0][0]
        for node in out_degree:
            if out_degree[node] - in_degree[node] == 1:
                start_node = node
                break
        
        path = []
        stack = [start_node]
        
        while stack:
            curr = stack[-1]
            if graph[curr]:
                next_node = graph[curr].popleft()
                stack.append(next_node)
            else:
                path.append(stack.pop())
        
        result = []
        for i in range(len(path) - 1, 0, -1):
            result.append([path[i], path[i-1]])
        
        return result

public class Solution {
    public int[][] ValidArrangement(int[][] pairs) {
        var graph = new Dictionary<int, Stack<int>>();
        var inDegree = new Dictionary<int, int>();
        var outDegree = new Dictionary<int, int>();
        
        // 构建图和计算度数
        foreach (var pair in pairs) {
            int start = pair[0], end = pair[1];
            
            if (!graph.ContainsKey(start)) graph[start] = new Stack<int>();
            graph[start].Push(end);
            
            outDegree[start] = outDegree.GetValueOrDefault(start, 0) + 1;
            inDegree[end] = inDegree.GetValueOrDefault(end, 0) + 1;
        }
        
        // 找起点
        int startNode = pairs[0][0];
        foreach (var kvp in outDegree) {
            if (kvp.Value - inDegree.GetValueOrDefault(kvp.Key, 0) == 1) {
                startNode = kvp.Key;
                break;
            }
        }
        
        var path = new List<int>();
        var stack = new Stack<int>();
        stack.Push(startNode);
        
        while (stack.Count > 0) {
            int curr = stack.Peek();
            if (graph.ContainsKey(curr) && graph[curr].Count > 0) {
                int next = graph[curr].Pop();
                stack.Push(next);
            } else {
                path.Add(stack.Pop());
            }
        }
        
        var result = new int[pairs.Length][];
        for (int i = 0; i < pairs.Length; i++) {
            result[i] = new int[] { path[path.Count - 1 - i], path[path.Count - 2 - i] };
        }
        
        return result;
    }
}

var validArrangement = function(pairs) {
    const graph = new Map();
    const inDegree = new Map();
    const outDegree = new Map();
    
    // Build graph and calculate degrees
    for (const [start, end] of pairs) {
        if (!graph.has(start)) graph.set(start, []);
        graph.get(start).push(end);
        
        outDegree.set(start, (outDegree.get(start) || 0) + 1);
        inDegree.set(end, (inDegree.get(end) || 0) + 1);
        
        if (!outDegree.has(end)) outDegree.set(end, 0);
        if (!inDegree.has(start)) inDegree.set(start, 0);
    }
    
    // Find starting node (Eulerian path)
    let start = pairs[0][0];
    for (const node of outDegree.keys()) {
        if (outDegree.get(node) - inDegree.get(node) === 1) {
            start = node;
            break;
        }
    }
    
    // Hierholzer's algorithm
    const result = [];
    const stack = [start];
    
    while (stack.length > 0) {
        const curr = stack[stack.length - 1];
        if (graph.has(curr) && graph.get(curr).length > 0) {
            const next = graph.get(curr).pop();
            stack.push(next);
        } else {
            stack.pop();
            if (stack.length > 0) {
                result.push([stack[stack.length - 1], curr]);
            }
        }
    }
    
    return result.reverse();
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小说明
时间复杂度O(V + E)其中V是节点数，E是边数，每条边和每个节点都被访问常数次
空间复杂度O(V + E)存储图的邻接表、度数统计和DFS栈所需的空间

相关题目