【LeetCode】可能的二分法 Java 题解
题目描述
给定一组 n 人(编号为 1, 2, ..., n), 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人,那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ,其中 dislikes[i] = [ai, bi] ,表示不允许将编号为 ai 和 bi 的人归入同一组。当可以用这种方法将所有人分进两组时,返回 true;否则返回 false。
思路分析
今天的算法题目是图类型题目。题目需要判断是否可以分成任意大小的两组数据。分析题目,首先给出 n,表述编号从 1 开始到 n 的数据, dislikes[i] = [ai, bi], 表示 ai 和 bi 的不能归入同一组。我们可以以此为依据,分别以 ai, bi 为顶点建立不能归为同一组的图。
图建立好之后,我们在采取染色法。定义 color 数组,初始化每一个元素为 0,表示未染色。逐个遍历每一个元素, 标记颜色为 1,不喜欢的人标记为 2。当同一个元素颜色有冲突的时候,则返回 false。否则返回 true。
图的元素遍历,一般常见的方法是 BFS 和 DFS。DFS 全称是 Depth First Search,中文名是深度优先搜索,是一种用于遍历或搜索树或图的算法。所谓深度优先,就是说每次都尝试向更深的节点走。这个题目,我们使用 DFS 完成相应的逻辑。具体实现代码如下,供参考。
通过代码
总结
上述算法的时间复杂度是 O(n),空间复杂度是 O(n)
坚持算法每日一题,加油!我会继续更新,也欢迎算法爱好者一起交流学习。
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/267de99ba6c46e171e66b65be】。文章转载请联系作者。
评论