LEETCODE 952. Largest Component Size by Common Factor 白话算法分析

题目大意:

按公因数计算最大组件大小

给定一个由不同正整数的组成的非空数组 A,考虑下面的图:

  • 有 A.length 个节点,按从 A[0] 到 A[A.length - 1] 标记;
  • 只有当 A[i] 和 A[j] 共用一个大于 1 的公因数时,A[i] 和 A[j] 之间才有一条边。

返回图中最大连通组件的大小。

示例 1:

输入:[4,6,15,35]
输出:4

示例 2:

输入:[20,50,9,63]
输出:2

示例 3:

输入:[2,3,6,7,4,12,21,39]
输出:8

提示:

  1. 1 <= A.length <= 20000
  2. 1 <= A[i] <= 100000


如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=952

算法分析:

要想完全搞定这道题,首先必须要了解一下什么是并查集(Union-Find)。这里我尽量用些通俗易懂的语言跟大家分析明白,正好自己也能复习一遍。

Union-Find算法主要解决的就是路径问题。将相连的节点通过Union方法结合,另外通过Find方法确定两个节点是否相连。大致的思路就是,我们将需要连接的节点设置上相同的根,然后再看任意两个节点是否存在相同的根即可得知其是否相连。

举个例子来看,比如我们有五个节点分别叫做0,1,2,3,4。我们利用一个表(数组)来管理这些节点的根。在没有结合前,每个节点的根就是它们自己的index。

int[] roots = {0, 1, 2, 3, 4};

如果我们想将节点1和3结合,那么我们可以将节点3的根修改为1的根。(根据喜好,将1的根修改为3同样可以),所以数组roots就变成:

int[] roots = {0, 1, 2, 1, 4};

继续将节点0和2结合:

int[] roots = {0, 1, 0, 1, 4};

再将节点0和3结合:这时需要注意一下,因为是更改根的值,3的根是节点1,所以要将节点1的值变为0

// 将3的根变为0的根
int[] roots = {0, 0, 0, 1, 4};
// 或者也可以是将0的根变为3的根
int[] roots = {1, 1, 0, 1, 4};

所以结合方法可以写成:

void union(int i, int j) {
    int rooti = root(i); // 取得节点i的根节点
    int rootj = root(j); // 取得节点j的根节点
    roots[rooti] = rootj; // roots[rootj] = rooti;也可以
}

这时,实际上除了节点4之外,其他的4个节点1,2,3,4都是可以连通的。那么如何能判断他们是否联通呢?上文已经说过,只要他们拥有同一个根,那么就可以判定其是关联的。求根的方法很简单,只要看当前节点的值是否等于其index即可,如果不等,就是用当前的值作为index继续查找下去,直到相同为止。

// 查找根的方法
int root(int i) {
    while (roots[i] != i) {
        i = roots[i];
    }
    return i;
}

// int[] roots = {0, 0, 0, 1, 4};
// 例如节点4
// root[4] = 1, 4 != 1, 将index变为节点4的值也就是1
// root[1] = 0, 1 != 0, 将index变为节点1的值也就是0
// root[0] = 0, 0 == 0, 所以节点4的根是节点0

最后就是find方法,也就是判断两个节点是否相连:

boolean find(int i, int j) {
    return root(i) == root(j);
}

至此,并查集(Union-Find)的基本思路就分析完了,那么如何运用到我们这道题中来呢?本题给出了一个int数组,任意两个数相连接的条件是看其是否存在大于1的公约数(也叫公因数),那么我们可以将能够被某个公约数整除的数字都罗列出来,再将其union到一起,最后找出集合最大的那个即可。举例说明一下。比如:

int A[] = {2, 6, 9};

那么,能被2的约数有2,6的约数有2, 3和6,9的约数则有3和9,即:

// 约数 -> 数组A中能被该约数整除的数
2 -> {2, 6}
3 -> {6, 9}
6 -> {6}
9 -> {9}

我们按照Union-Find的思路先建立一个roots数组,因为A有三个元素,所以roots的长度也是3, 即:

int A[] = {2, 6, 9};
int roots[] = {0, 1, 2}

同一约数包含的数字集合肯定存在公约数,所以该集合都可以Union,我们先看约数2包含的集合是2和6,也就是index为0和1的两个元素,我们将其合并:

int A[] = {2, 6, 9};
int roots[] = {0, 0, 2}

继续看约数3包含的集合,其中有6和9,我们将其合并,因为6也同时出现在了约数2的集合中,所以,合并6和9的同时,数字2也同时与其变为同一根。

int A[] = {2, 6, 9};
int roots[] = {0, 0, 0} // 同样可合并为{2, 0, 2}

之后的集合由于只包含一个数字,所以无需合并了。

所有的Union操作结束之后,我们可以遍历整个roots数组,算出所有节点的根,拥有子节点最多的根的所有节点数就是题目的结果。

最后看看完整的代码:

int[] roots; // Union-find要用到的数组

public int largestComponentSize(int[] A) {
    // A数组长度
    int length = A.length;
    // 初始化roots数组
    roots = new int[length];
    for (int index = 0; index < length; index++) {
        // 每个元素的根都设置为其自身在A中的index
        roots[index] = index;
    }
    // 用于存储每个约数对应的可以被该约数整除的A中元素的inedx
    Map<Integer, Set<Integer>> factorMap = new HashMap<>();
    // 遍历A中所有数字
    for (int index = 0; index < length; index++) {
        int a = A[index];
        // 因为A中每个数字最大为10万,遍历次数太多,所以在此做开方处理
        // 这一步非常关键,如果不做这个处理,代码执行时间会大幅增加
        // 不明白的,先别着急,继续向下看代码,文章最后会有详细的分析
        int upper = (int) Math.sqrt(a);
        // 因为数字a本身也是其约数,所以先将a的index加入到集合中
        Set<Integer> indexSet0 = factorMap.getOrDefault(a, new HashSet<>());
        indexSet0.add(index);
        factorMap.put(a, indexSet0);
        // 从2循环至upper,看哪些数字可以被a整除
        for (int factor = 2; factor <= upper; factor++) {
            // 如果可以整除
            if (a % factor == 0) {
                // 将a的index添加到该约数对应的集合中
                Set<Integer> indexSet = factorMap.getOrDefault(factor, new HashSet<>());
                indexSet.add(index);
                factorMap.put(factor, indexSet);
                // 将该约数除干净,到不能整除为止
                while (a % factor == 0) {
                    a = a / factor;
                    // 如果除法结果不为1,那么结果也是该数字的约数之一,
                    // 同样需要将a的index存入该约数对应的集合
                    if (a != 1) {
                        Set<Integer> indexSet2 = factorMap.getOrDefault(a, new HashSet<>());
                        indexSet2.add(index);
                        factorMap.put(a, indexSet2);
                    }
                }
                // 因为除了自身之外的约数一定小于等于其自身的一半,
                // 为了减少循环次数,此处可以break
                if (a < factor * 2) {
                        break;
                }
            }
        }
    }
    // 所有约数对应的A中数字整理完之后,开始Union操作
    for (Map.Entry<Integer, Set<Integer>> entrySet : factorMap.entrySet()) {
        // 循环取出所有约数,对应的集合,因为他们存在同一约数,所以可以合并
        Set<Integer> set = entrySet.getValue();
        if (set.size() > 1) {
            int i = -1;
            // 先取出集合中的第一个数字
            for (Integer seti : set) {
                set.remove(seti);
                i = seti;
                break;
            }
            // 再将第一个数字与其他数字Union
            for (Integer j : set) {
                union(i, j);
            }
        }
    }
    // Union操作结束后,开始统计每个根拥有的节点数量
    Map<Integer, Integer> rootCountMap = new HashMap<>();
    for (int root : roots) {
        // 当前节点的根拥有的全部节点数量。
        int count = rootCountMap.getOrDefault(root(root), 0);
        // 将当前节点算入其数量中(节点数加一)
        rootCountMap.put(root(root), count + 1);
    }

    // 统计完每个根拥有的节点数量后,找出数量最大的即是结果
    int res = 0;
    for (Map.Entry<Integer, Integer> entrySet : rootCountMap.entrySet()) {
        res = Math.max(res, entrySet.getValue());
    }
    return res;
}

int root(int i) {
    while (roots[i] != i) {
        i = roots[i];
    }
    return i;
}

void union(int i, int j) {
    int rooti = root(i);
    int rootj = root(j);
    roots[rooti] = rootj;
}

总结:

其实本题的解法并没有用到find方法,因为union之后就可以统计出结果了。另外本题的算法还可以再进行优化,比如边Union边统计等,由于时间原因,就不展开分析了。

最后再说说代码中提到的开方处理。简单来说,求一个数字所有约数的方法可以从1循环到其本身,可以被整除的都是它的约数。比如说36,我们从1循环到36,可以得到1,2,3,4,6,9,12,18,36这些质数。这需要循环36次。优化一下思路,其实除去数字本身之外的约数,一定是小于其自身一半的,其实循环18次再加上数字本身就可以。虽然对于当今高性能的计算机来说,循环18次和36次所用时间的差别几乎可以忽略不计,但是如果数字很大,比如36兆,那么,差别就会变得非常明显。

但这远远不是最优解,再优化一下我们的思路,来看看36的这些质数,除了1和36本身之外,其他的所有质数2,3,4,6,9,12,从两边到中间都是可以两两相乘等于36的,也就是说,当我们得到最小质数2的同时,也就知道了最大质数一定是18,这组质数的中点就是36的平方根6,所以,当我们知道了6之前的所有质数时,6之后的也都相应得出了,这就是为什么要开方的原因。当然不能以正数开方的数字同样适用这个规则。这一点,大家需要自己整理一下的逻辑。所以我们的时间复杂度可以从O(n)精简到O(sqrt(n))

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-952-largest-component-size-by-common-factor-白话算法分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。