最大公约数遍历
难度:
标签:
题目描述
You are given a 0-indexed integer array nums, and you are allowed to traverse between its indices. You can traverse between index i and index j, i != j, if and only if gcd(nums[i], nums[j]) > 1, where gcd is the greatest common divisor.
Your task is to determine if for every pair of indices i and j in nums, where i < j, there exists a sequence of traversals that can take us from i to j.
Return true if it is possible to traverse between all such pairs of indices, or false otherwise.
Example 1:
Input: nums = [2,3,6] Output: true Explanation: In this example, there are 3 possible pairs of indices: (0, 1), (0, 2), and (1, 2). To go from index 0 to index 1, we can use the sequence of traversals 0 -> 2 -> 1, where we move from index 0 to index 2 because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1, and then move from index 2 to index 1 because gcd(nums[2], nums[1]) = gcd(6, 3) = 3 > 1. To go from index 0 to index 2, we can just go directly because gcd(nums[0], nums[2]) = gcd(2, 6) = 2 > 1. Likewise, to go from index 1 to index 2, we can just go directly because gcd(nums[1], nums[2]) = gcd(3, 6) = 3 > 1.
Example 2:
Input: nums = [3,9,5] Output: false Explanation: No sequence of traversals can take us from index 0 to index 2 in this example. So, we return false.
Example 3:
Input: nums = [4,3,12,8] Output: true Explanation: There are 6 possible pairs of indices to traverse between: (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), and (2, 3). A valid sequence of traversals exists for each pair, so we return true.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105
代码结果
运行时间: 70 ms, 内存: 29.7 MB
/*
* 思路：
* 使用 Java Stream 的方式来处理 gcdMap 的生成，并使用并查集进行连通性检查。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public boolean canTraverseAllPairs(int[] nums) {
int n = nums.length;
UnionFind uf = new UnionFind(n);
Map<Integer, List<Integer>> gcdMap = IntStream.range(0, n)
.boxed()
.flatMap(i -> getPrimeFactors(nums[i]).stream().map(f -> new AbstractMap.SimpleEntry<>(f, i)))
.collect(Collectors.groupingBy(Map.Entry::getKey, Collectors.mapping(Map.Entry::getValue, Collectors.toList())));
gcdMap.values().forEach(list -> IntStream.range(1, list.size()).forEach(i -> uf.union(list.get(0), list.get(i))));
return uf.count() == 1;
}
private List<Integer> getPrimeFactors(int num) {
List<Integer> factors = new ArrayList<>();
for (int i = 2; i <= Math.sqrt(num); i++) {
if (num % i == 0) {
factors.add(i);
while (num % i == 0) num /= i;
}
}
if (num > 1) factors.add(num);
return factors;
}
class UnionFind {
private int[] parent, rank;
private int count;
public UnionFind(int n) {
parent = new int[n];
rank = new int[n];
count = n;
IntStream.range(0, n).forEach(i -> parent[i] = i);
}
public int find(int p) {
if (parent[p] != p) parent[p] = find(parent[p]);
return parent[p];
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP != rootQ) {
if (rank[rootP] > rank[rootQ]) {
parent[rootQ] = rootP;
} else if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
}
public int count() {
return count;
}
}
}解释
方法:
The given solution tries to determine if any pair of indices in the array can be traversed using the greatest common divisor (gcd) condition. It first checks trivial cases such as single-element arrays and arrays containing the number '1'. Afterwards, it removes duplicates and sorts the array in descending order. The code then attempts to check if, for each element, there exists another element with a gcd greater than 1. If it finds such a pair, it modifies the second element by multiplying it with the first, presumably to increase future gcd values artificially. If it cannot find any such pair for any element, it returns False, otherwise True if all elements can be paired up successfully.
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
为什么在算法中要先去除数组中的重复元素并进行排序？
▷🦆
在解题思路中提到，如果数组中存在数字1，就直接返回False。请问这样做的理由是什么？
▷🦆
算法中提到将满足条件的第二个元素乘以第一个元素，这样做的目的和效果是什么？
▷🦆
对于修改数组元素的操作，为什么只修改了`nums[j]`而没有修改`nums[i]`？这样的操作是否会影响算法的正确性？
▷