Hard
题目描述
给你一个下标从 0 开始的整数数组 nums ，你可以在其索引之间进行遍历。当且仅当 gcd(nums[i], nums[j]) > 1 时，你可以从索引 i 遍历到索引 j（其中 i != j），这里 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 <= 10^51 <= nums[i] <= 10^5
解题思路
这道题的核心思想是将问题转化为图的连通性问题。两个索引之间可以遍历当且仅当对应数值的最大公约数大于1，即它们有公共质因数。
思路分析：
建图思路：将每个数的所有质因数作为桥梁。如果两个数有公共质因数，它们就能相互到达。
优化策略：不需要直接计算所有数对的最大公约数，而是通过质因数分解来建立连接关系。对于每个质因数，将包含该质因数的所有数的索引连接起来。
连通性检查：使用并查集判断所有索引是否在同一个连通分量中。
具体步骤：
- 预处理：使用埃拉托色尼筛法找出所有小于等于10^5的质数
- 对每个数进行质因数分解
- 对于每个质因数，将包含该质因数的所有索引通过并查集连接
- 检查所有索引是否在同一连通分量中
特殊情况处理：
- 如果数组只有一个元素，直接返回true
- 如果数组中包含1，且数组长度大于1，返回false（因为1与任何数的最大公约数都是1）
代码实现
class Solution {
public:
bool canTraverseAllPairs(vector<int>& nums) {
int n = nums.size();
if (n == 1) return true;
// 检查是否有1
for (int num : nums) {
if (num == 1) return false;
}
// 并查集
vector<int> parent(n);
iota(parent.begin(), parent.end(), 0);
function<int(int)> find = [&](int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
};
auto unite = [&](int x, int y) {
x = find(x), y = find(y);
if (x != y) parent[y] = x;
};
// 质因数到第一个出现位置的映射
unordered_map<int, int> factorToIndex;
for (int i = 0; i < n; i++) {
int num = nums[i];
// 质因数分解
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
if (factorToIndex.count(p)) {
unite(i, factorToIndex[p]);
} else {
factorToIndex[p] = i;
}
while (num % p == 0) {
num /= p;
}
}
}
if (num > 1) {
if (factorToIndex.count(num)) {
unite(i, factorToIndex[num]);
} else {
factorToIndex[num] = i;
}
}
}
// 检查是否所有索引都在同一连通分量
int root = find(0);
for (int i = 1; i < n; i++) {
if (find(i) != root) return false;
}
return true;
}
};
class Solution:
def canTraverseAllPairs(self, nums: List[int]) -> bool:
n = len(nums)
if n == 1:
return True
# 检查是否有1
if 1 in nums:
return False
# 并查集
parent = list(range(n))
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def unite(x, y):
px, py = find(x), find(y)
if px != py:
parent[py] = px
# 质因数到第一个出现位置的映射
factor_to_index = {}
for i, num in enumerate(nums):
# 质因数分解
p = 2
while p * p <= num:
if num % p == 0:
if p in factor_to_index:
unite(i, factor_to_index[p])
else:
factor_to_index[p] = i
while num % p == 0:
num //= p
p += 1
if num > 1:
if num in factor_to_index:
unite(i, factor_to_index[num])
else:
factor_to_index[num] = i
# 检查是否所有索引都在同一连通分量
root = find(0)
for i in range(1, n):
if find(i) != root:
return False
return True
public class Solution {
public bool CanTraverseAllPairs(int[] nums) {
int n = nums.Length;
if (n == 1) return true;
// 检查是否有1
foreach (int num in nums) {
if (num == 1) return false;
}
// 并查集
int[] parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int Find(int x) {
if (parent[x] != x) {
parent[x] = Find(parent[x]);
}
return parent[x];
}
void Unite(int x, int y) {
int px = Find(x), py = Find(y);
if (px != py) parent[py] = px;
}
// 质因数到第一个出现位置的映射
var factorToIndex = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
int num = nums[i];
// 质因数分解
for (int p = 2; p * p <= num; p++) {
if (num % p == 0) {
if (factorToIndex.ContainsKey(p)) {
Unite(i, factorToIndex[p]);
} else {
factorToIndex[p] = i;
}
while (num % p == 0) {
num /= p;
}
}
}
if (num > 1) {
if (factorToIndex.ContainsKey(num)) {
Unite(i, factorToIndex[num]);
} else {
factorToIndex[num] = i;
}
}
}
// 检查是否所有索引都在同一连通分量
int root = Find(0);
for (int i = 1; i < n; i++) {
if (Find(i) != root) return false;
}
return true;
}
}
var canTraverseAllPairs = function(nums) {
const n = nums.length;
if (n === 1) return true;
// Union-Find
const parent = Array.from({length: n}, (_, i) => i);
const rank = new Array(n).fill(0);
function find(x) {
if (parent[x] !== x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
function union(x, y) {
const px = find(x), py = find(y);
if (px === py) return;
if (rank[px] < rank[py]) {
parent[px] = py;
} else if (rank[px] > rank[py]) {
parent[py] = px;
} else {
parent[py] = px;
rank[px]++;
}
}
// Get prime factors
function getPrimeFactors(num) {
const factors = new Set();
let d = 2;
while (d * d <= num) {
while (num % d === 0) {
factors.add(d);
num /= d;
}
d++;
}
if (num > 1) factors.add(num);
return factors;
}
// Map prime factors to indices
const primeToIndices = new Map();
for (let i = 0; i < n; i++) {
if (nums[i] === 1) return false; // 1 can't connect to anything
const primes = getPrimeFactors(nums[i]);
for (const prime of primes) {
if (!primeToIndices.has(prime)) {
primeToIndices.set(prime, []);
}
primeToIndices.get(prime).push(i);
}
}
// Union indices that share prime factors
for (const indices of primeToIndices.values()) {
for (let i = 1; i < indices.length; i++) {
union(indices[0], indices[i]);
}
}
// Check if all indices are in the same component
const root = find(0);
for (let i = 1; i < n; i++) {
if (find(i) !== root) return false;
}
return true;
};
复杂度分析
| 复杂度类型 | 分析 |
|---|---|
| 时间复杂度 | O(n√m + nα(n))，其中 n 是数组长度，m 是数组中的最大值，α 是阿克曼函数的反函数 |
| 空间复杂度 | O(n + k)，其中 k 是不同质因数的数量 |