### 题目 有一个无向的 星型 图，由 n 个编号从 1 到 n 的节点组成。星型图有一个 中心 节点，并且恰有 n - 1 条边将中心节点与其他每个节点连接起来。 给你一个二维整数数组 edges ，其中 edges[i] = [ui, vi] 表示在节点 ui 和 vi 之间存在一条边。请你找出并返回 edges 所表示星型图的中心节点。 ### 输入输出 #### 示例1  ``` 输入：edges = [[1,2],[2,3],[4,2]] 输出：2 解释：如上图所示，节点 2 与其他每个节点都相连，所以节点 2 是中心节点。 ``` #### 示例2 ``` 输入：edges = [[1,2],[5,1],[1,3],[1,4]] 输出：1 ``` **提示** 3 <= n <= 10^5 edges.length == n - 1 edges[i].length == 2 1 <= ui, vi <= n ui != vi 题目数据给出的 edges 表示一个有效的星型图 ### 题目解答 #### 思路 1. 由于所有边都与其中一个顶点相连，因此任选其中2条边，就可以确定中心顶点。 2. 不妨选前2条边，每条边2个顶点, [[u1, v1][u2, v2]]。将其视作二分图，一共四种组合方式，其中一定有一种组合选择都是中心顶点。 **复杂度** 时间复杂度：需要考察4对顶点是否相等，复杂度O(1) 空间复杂度：无需新的空间，O(1) #### 代码实现 ```java class Solution { public int findCenter(int[][] edges) { if(edges[0][0]==edges[1][0]) return edges[0][0]; else if(edges[0][1]==edges[1][0]) return edges[0][1]; else if(edges[0][1]==edges[1][1]) return edges[0][1]; else if(edges[0][0]==edges[1][1]) return edges[0][0]; else return -1; } } ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复