2097. 合法重新排列数对

🔴   🔖  深度优先搜索 图 欧拉回路  🔗 力扣 LeetCode

题目

You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endi-1 == starti.

Return _any valid arrangement of _pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]

Output: [[11,9],[9,4],[4,5],[5,1]]

Explanation: This is a valid arrangement since endi-1 always equals starti.

end0 = 9 == 9 = start1

end1 = 4 == 4 = start2

end2 = 5 == 5 = start3

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]

Output: [[1,3],[3,2],[2,1]]

Explanation:

This is a valid arrangement since endi-1 always equals starti.

end0 = 3 == 3 = start1

end1 = 2 == 2 = start2

The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]

Output: [[1,2],[2,1],[1,3]]

Explanation:

This is a valid arrangement since endi-1 always equals starti.

end0 = 2 == 2 = start1

end1 = 1 == 1 = start2

Constraints:

• 1 <= pairs.length <= 10^5
• pairs[i].length == 2
• 0 <= starti, endi <= 10^9
• starti != endi
• No two pairs are exactly the same.
• There exists a valid arrangement of pairs.

题目大意

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

解题思路

相关知识：欧拉路径和欧拉回路

1. 欧拉路径:

   • 是一种路径，它能够遍历图中的所有边，且每条边恰好遍历一次。
   • 对于欧拉路径的图，满足的条件：
     • 最多有两个特殊的节点：一个节点的出度比入度多 1（起点），一个节点的入度比出度多 1（终点）。
     • 其他节点的出度等于入度。

2. 欧拉回路:

   • 是一种路径，它能够遍历图中的所有边且回到起点，形成一个回路。
   • 条件是：所有节点的出度等于入度。

为了找到一个合法的路径，可以通过以下步骤：

1. 构建图

使用邻接表表示图，记录每个节点的出度和入度：

• 邻接表存储图中的边，方便遍历。
• 出度和入度记录每个节点的出入情况，帮助判断起点或终点。

2. 确定起点

• 如果存在出度比入度多 1 的节点，起点就是它。
• 如果所有节点的出度等于入度，可以任选一个有边的节点作为起点。

3. Hierholzer 算法构建欧拉路径

Hierholzer 算法用于构建欧拉路径或欧拉回路：

1. 从起点开始，尽可能深地访问节点。
2. 当无法继续时，将节点加入路径，并回溯。
3. 最后得到的路径是倒序的，需翻转为正序。

复杂度分析

• 时间复杂度：O(E)，其中 E 是边的数量，需要构建图以及深度优先搜索遍历所有边。
• 空间复杂度：O(V + E)，其中 V 是节点数，用于存储邻接表和入出度。

代码

var validArrangement = function (pairs) {
	// Step 1: 构建图、出度和入度
	const graph = new Map(); // 邻接表
	const outDegree = new Map();
	const inDegree = new Map();

	for (const [u, v] of pairs) {
		if (!graph.has(u)) graph.set(u, []);
		graph.get(u).push(v);

		outDegree.set(u, (outDegree.get(u) || 0) + 1);
		inDegree.set(v, (inDegree.get(v) || 0) + 1);
	}

	// Step 2: 确定起点
	let start = pairs[0][0]; // 默认起点
	for (const [node, out] of outDegree) {
		const inD = inDegree.get(node) || 0;
		if (out > inD) {
			start = node; // 出度大于入度的节点是起点
			break;
		}
	}

	// Step 3: 使用 Hierholzer 算法构建路径
	const result = [];
	const dfs = (node) => {
		const edges = graph.get(node) || [];
		while (edges.length > 0) {
			const next = edges.pop(); // 移除一条边
			dfs(next); // 递归访问下一节点
		}
		result.push(node); // 回溯时记录路径
	};

	dfs(start);

	// Step 4: 翻转路径并返回
	return result
		.reverse()
		.slice(0, -1)
		.map((v, i) => [v, result[i + 1]]);
};

相关题目

题号	标题	题解	标签	难度	力扣
332	重新安排行程		深度优先搜索 图 欧拉回路	🔴	🀄️ 🔗
1971	寻找图中是否存在路径	[✓]	深度优先搜索 广度优先搜索 并查集 1+	🟢	🀄️ 🔗