LeetCode 题解工作台
最大公约数遍历
给你一个下标从 0 开始的整数数组 nums ，你可以在一些下标之间遍历。对于两个下标 i 和 j （ i != j ），当且仅当 gcd(nums[i], nums[j]) > 1 时，我们可以在两个下标之间通行，其中 gcd 是两个数的 最大公约数 。 你需要判断 nums 数组中 任意 两个满…
4
题型
4
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
答案摘要
class UnionFind: def __init__(self, n):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个下标从 0 开始的整数数组 nums ，你可以在一些下标之间遍历。对于两个下标 i 和 j（i != j），当且仅当 gcd(nums[i], nums[j]) > 1 时，我们可以在两个下标之间通行，其中 gcd 是两个数的 最大公约数 。
你需要判断 nums 数组中 任意 两个满足 i < j 的下标 i 和 j ，是否存在若干次通行可以从 i 遍历到 j 。
如果任意满足条件的下标对都可以遍历，那么返回 true ，否则返回 false 。
示例 1：
输入：nums = [2,3,6] 输出：true 解释：这个例子中，总共有 3 个下标对：(0, 1) ，(0, 2) 和 (1, 2) 。 从下标 0 到下标 1 ，我们可以遍历 0 -> 2 -> 1 ，我们可以从下标 0 到 2 是因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 ，从下标 2 到 1 是因为 gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1 。 从下标 0 到下标 2 ，我们可以直接遍历，因为 gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1 。同理，我们也可以从下标 1 到 2 因为 gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1 。
示例 2：
输入：nums = [3,9,5] 输出：false 解释：我们没法从下标 0 到 2 ，所以返回 false 。
示例 3：
输入：nums = [4,3,12,8] 输出：true 解释：总共有 6 个下标对：(0, 1) ，(0, 2) ，(0, 3) ，(1, 2) ，(1, 3) 和 (2, 3) 。所有下标对之间都存在可行的遍历，所以返回 true 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 105
解题思路
方法一
class UnionFind:
def __init__(self, n):
self.p = list(range(n))
self.size = [1] * n
def find(self, x):
if self.p[x] != x:
self.p[x] = self.find(self.p[x])
return self.p[x]
def union(self, a, b):
pa, pb = self.find(a), self.find(b)
if pa == pb:
return False
if self.size[pa] > self.size[pb]:
self.p[pb] = pa
self.size[pa] += self.size[pb]
else:
self.p[pa] = pb
self.size[pb] += self.size[pa]
return True
mx = 100010
p = defaultdict(list)
for x in range(1, mx + 1):
v = x
i = 2
while i <= v // i:
if v % i == 0:
p[x].append(i)
while v % i == 0:
v //= i
i += 1
if v > 1:
p[x].append(v)
class Solution:
def canTraverseAllPairs(self, nums: List[int]) -> bool:
n = len(nums)
m = max(nums)
uf = UnionFind(n + m + 1)
for i, x in enumerate(nums):
for j in p[x]:
uf.union(i, j + n)
return len(set(uf.find(i) for i in range(n))) == 1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n*log(MAX_VAL)) due to factoring each element and performing union operations. Space complexity is O(n) for storing union-find parent arrays and factor-index mappings. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Looking for correct factorization strategy and mapping.
- question_mark
Expecting union-find implementation with path compression.
- question_mark
Checking understanding of GCD-based connectivity and edge cases like 1 or primes.
常见陷阱
外企场景- error
Failing to connect all indices sharing the same prime factor.
- error
Ignoring numbers equal to 1 that break connectivity.
- error
Inefficient factorization causing TLE on large arrays.
进阶变体
外企场景- arrow_right_alt
Allow traversal if gcd >= k instead of >1, changing connectivity conditions.
- arrow_right_alt
Array contains repeated numbers, testing union-find handling of duplicates.
- arrow_right_alt
Input with maximum values, emphasizing sieve and factorization optimizations.