N 个组有一个可以选择的数字列表。如果一组选择数字 i，则确定是否所有组都能够选择一个数字
假设有一个组，每个组都有可以选择的数字。
Group 1: [1, 2, 3, 4],
Group 2: [2, 3, 4],
Group 3: [2, 3, 4],
Group 4: [4]
假设第 4 组最初在其列表中选择 4。现在，其他组不能使用 4。一种可能的排列是组 1 选择 1，组 3 选择 2，组 2 选择 3。但是，如果组 1 最初选择 4，则不存在有效的排列，因为第 4 组唯一可以使用的数字是 4。由于 4 已被第 1 组使用，因此第 4 组不能选择任何数字，因此并非每个组都可以选择数字。如果给定组 N 选择他们可以选择的数字 i，则返回 true 或 false，所有其余组都可以选择一个数字。是否有高效的 O(n) 或 O(n^2) 算法？
我的解决方案尝试/想法：
最初，我认为也许可以将其转换为有向图表示，并确定是否有一种方法可以从另一个节点遍历所有节点。然而，这意味着涉及循环，而且这是多项式。
Say that there is a group, each with numbers that it can pick.
Group 1: [1, 2, 3, 4],
Group 2: [2, 3, 4],
Group 3: [2, 3, 4],
Group 4: [4]
Say that it initially Group 4 chooses 4 in its list. Now, other groups can't use a 4. One possible arrangement is group 1 chooses the 1, group 3 chooses the 2, and group 2 chooses the 3. However, if group 1 initially chooses 4, there is no valid arrangement, since the only number group 4 can use is 4. Since 4 was used by group 1, group 4 can't choose any numbers, and thus not every group can choose a number. Return true or false if given that group N chooses a number i that they can pick, all the rest of the groups can choose a number. Is there an efficient O(n) or O(n^2) algorithm?
My solution attempt/thoughts:
Originally, I thought that maybe converting this into a directed graph representation and determining if there is a way for all nodes to be traversed to from another node. However, this would mean there are loops involved, and also this is polynomial.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论