题目描述
有 n
座城市,编号从 1
到 n
。编号为 x
和 y
的两座城市直接连通的前提是: x
和 y
的公因数中,至少有一个 严格大于 某个阈值 threshold
。更正式地说,如果存在整数 z
,且满足以下所有条件,则编号 x
和 y
的城市之间有一条道路:
x % z == 0
y % z == 0
z > threshold
给你两个整数 n
和 threshold
,以及一个待查询数组,请你判断每个查询 queries[i] = [ai, bi]
指向的城市 ai
和 bi
是否连通(即,它们之间是否存在一条路径)。
返回数组 answer
,其中answer.length == queries.length
。如果第 i
个查询中指向的城市 ai
和 bi
连通,则 answer[i]
为 true
;如果不连通,则 answer[i]
为 false
。
样例
输入:n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
输出:[false,false,true]
解释:每个数的因数如下:
1: 1
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
所有大于阈值的的因数已经加粗标识,只有城市 3 和 6 共享公约数 3 ,因此结果是:
[1,4] 1 与 4 不连通
[2,5] 2 与 5 不连通
[3,6] 3 与 6 连通,存在路径 3--6
输入:n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
输出:[true,true,true,true,true]
解释:每个数的因数与上一个例子相同。但是,由于阈值为 0 ,所有的因数都大于阈值。
因为所有的数字共享公因数 1 ,所以所有的城市都互相连通。
算法分析
并查集
x
与y
之间存在大于t
的约数 等价于 x
与 y
之间有边
如何高效建图?(直接两重循环枚举求gcd
时间复杂度是$O(n^2logn)$,会超时)
所有满足题意的约数有[t + 1, n]
,假设d
是区间中其中一个约数,则公约数是d
的序列有d, 2d, 3d, 4d, ... kd
,将该序列的元素形成一个集合,共有 $\frac{n}{d}$ 个,则[t + 1, n]
区间的所有约数个数有 $\frac{n}{t + 1} + \frac{n}{t + 2} + … + \frac{n}{n} <= n (1 + \frac{1}{2} + \frac{1}{3} + … + \frac{1}{n}) = O(nlogn)$
步骤
- 1、建图,从
d = t + 1
开始到n
,枚举出所有不大于n
的d
的倍数,将该序列合并成一个集合 - 2、遍历所有的访问,返回
a
元素的根结点和b
元素的根结点是否一样即可,将结果加入到链表中
时间复杂度
参考文献
y总
Java 代码
class Solution {
static int N = 10000 + 10;
static int[] p = new int[N];
static int find(int x)
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
for(int i = 1;i <= n;i ++) p[i] = i;
for(int i = threshold + 1;i <= n;i ++)
for(int d = i * 2;d <= n;d += i)
p[find(d)] = find(i);
List<Boolean> res = new ArrayList<Boolean>();
for(int i = 0;i < queries.length;i ++)
{
int a = queries[i][0];
int b = queries[i][1];
res.add(find(a) == find(b));
}
return res;
}
}