[Swift Weekly Contest 113]LeetCode952. 按公因数计算最大组件

发布时间：2020-12-14 05:09:25 所属栏目：百科来源：网络整理

导读：Given a non-empty?array of unique positive integers? A ,consider the following graph: There are? A.length ?nodes,labelled? A[0] ?to? A[A.length - 1]; There is an edge between? A[i] ?and? A[j] ?if and only if? A[i] ?and? A[j] ?share a commo

Given a non-empty?array of unique positive integers?A,consider the following graph:

There are?A.length?nodes,labelled?A[0]?to?A[A.length - 1];
There is an edge between?A[i]?and?A[j]?if and only if?A[i]?and?A[j]?share a common factor greater than 1.

Return the size of the largest connected component in the graph.

Example 1:

Input: [4,6,15,35]
Output: 4

Example 2:

Input: [20,50,9,63]
Output: 2

Example 3:

Input: [2,3,7,4,12,21,39]
Output: 8

Note:

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

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

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

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

示例 1：

输入：[4,35]
输出：4

示例 2：

输入：[20,63]
输出：2

示例 3：

输入：[2,39]
输出：8

提示：

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

3332 ms?

  1 class Solution {
  2     func largestComponentSize(_ A: [Int]) -> Int {
  3         var lpf:[Int] = enumLowestPrimeFactors(100001)
  4         var ds:DJSet = DJSet(100001)
  5         for v in A
  6         {
  7             ds.w[v] = 1
  8         }
  9         for v in A
 10         {
 11             var vv:Int = v
 12             while(vv > 1)
 13             {
 14                 ds.union(v,lpf[vv])
 15                 vv /= lpf[vv]
 16             }
 17         }
 18         var ret:Int = 0
 19         for i in 1...100000
 20         {
 21             if ds.upper[i] < 0
 22             {
 23                 ret = max(ret,ds.w[i])
 24             }
 25         }
 26         return ret
 27     }
 28     
 29     func enumLowestPrimeFactors(_ n:Int) -> [Int]
 30     {
 31         var tot:Int = 0
 32         var lpf:[Int] = [Int](repeating:0,count:n + 1)
 33         var u:Double = Double(n + 32)
 34         var lu:Double = log(u)
 35         let num:Int = Int(u / lu + u / lu / lu * 1.5)
 36         var primes:[Int] = [Int](repeating:0,count:num)
 37         for i in 2...n
 38         {
 39             lpf[i] = i
 40         }
 41         for p in 2...n
 42         {
 43             if lpf[p] == p
 44             {
 45                 primes[tot] = p
 46                 tot += 1
 47             }
 48             var tmp:Int = 0
 49             var i:Int = 0
 50             while(i < tot && primes[i] <= lpf[p] && primes[i] * p <= n)
 51             {
 52                 tmp = primes[i] * p
 53                 lpf[tmp] = primes[i]
 54                 i += 1
 55             }
 56         }
 57         return lpf
 58     }
 59 }
 60 public class DJSet
 61 {
 62     var upper:[Int]
 63     var w:[Int]
 64     
 65     init(_ n:Int)
 66     {
 67         upper = [Int](repeating:-1,count:n)
 68         w = [Int](repeating:0,count:n)
 69     }
 70     
 71     func root(_ x:Int) -> Int
 72     {
 73         if(upper[x] < 0)
 74         {
 75             return x
 76         }
 77         else
 78         {
 79             upper[x] = root(upper[x])
 80             return upper[x]
 81         }
 82     }
 83     
 84     func equiv(_ x:Int,_ y:Int) -> Bool
 85     {
 86         return root(x) == root(y)
 87     }
 88     
 89     func union(_ x:Int,_ y:Int) -> Bool
 90     {
 91         var x:Int = root(x)
 92         var y:Int = root(y)
 93         if x != y
 94         {
 95             if upper[y] < upper[x]
 96             {
 97                 var d:Int = x
 98                 x = y
 99                 y = d
100             }
101             upper[x] += upper[y]
102             upper[y] = x
103             w[x] += w[y]
104         }
105         return x == y
106     }
107     
108     func count() -> Int
109     {
110         var ct:Int = 0
111         for u in upper
112         {
113             if u < 0
114             {
115                 ct += 1
116             }
117         }
118         return ct
119     }
120 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!