[Swift Weekly Contest 113]LeetCode952. 按公因数计算最大组件大小 | Largest Component Size by Common Factor

概述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

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 @H_@R_301_6940@_158@class Solution {  2     func largestComponentSize(_ A: [Int]) -> Int {  3         @H_@R_301_6940@_158@var lpf:[Int] = enumLowestPrimeFactors(100001)  4         @H_@R_301_6940@_158@var ds:DJset = DJset(100001)  5         @H_@R_301_6940@_158@for v @H_@R_301_6940@_158@in A  6         {  7             ds.w[v] = 1  8         }  9         @H_@R_301_6940@_158@for v @H_@R_301_6940@_158@in A 10         { 11             @H_@R_301_6940@_158@var vv:Int = v 12             @H_@R_301_6940@_158@while(vv > 1) 13             { 14                 ds.union(v,lpf[vv]) 15                 vv /= lpf[vv] 16             } 17         } 18         @H_@R_301_6940@_158@var ret:Int = 0 19         @H_@R_301_6940@_158@for i @H_@R_301_6940@_158@in 1...100000 20         { 21             @H_@R_301_6940@_158@if ds.upper[i] < 0 22             { 23                 ret = max(ret,ds.w[i]) 24             } 25         } 26         @H_@R_301_6940@_158@return ret 27     } 28      29     func enumLowestPrimeFactors(_ n:Int) -> [Int] 30     { 31         @H_@R_301_6940@_158@var tot:Int = 0 32         @H_@R_301_6940@_158@var lpf:[Int] = [Int](repeating:0,count:n + 1) 33         @H_@R_301_6940@_158@var u:Double = Double(n + 32) 34         @H_@R_301_6940@_158@var lu:Double = log(u) 35         let num:Int = Int(u / lu + u / lu / lu * 1.5) 36         @H_@R_301_6940@_158@var primes:[Int] = [Int](repeating:0,count:num) 37         @H_@R_301_6940@_158@for i @H_@R_301_6940@_158@in 2...n 38         { 39             lpf[i] = i 40         } 41         @H_@R_301_6940@_158@for p @H_@R_301_6940@_158@in 2...n 42         { 43             @H_@R_301_6940@_158@if lpf[p] == p 44             { 45                 primes[tot] = p 46                 tot += 1 47             } 48             @H_@R_301_6940@_158@var tmp:Int = 0 49             @H_@R_301_6940@_158@var i:Int = 0 50             @H_@R_301_6940@_158@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         @H_@R_301_6940@_158@return lpf 58     } 59 } 60 @H_@R_301_6940@_158@public @H_@R_301_6940@_158@class DJset 61 { 62     @H_@R_301_6940@_158@var upper:[Int] 63     @H_@R_301_6940@_158@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         @H_@R_301_6940@_158@if(upper[x] < 0) 74         { 75             @H_@R_301_6940@_158@return x 76         } 77         @H_@R_301_6940@_158@else 78         { 79             upper[x] = root(upper[x]) 80             @H_@R_301_6940@_158@return upper[x] 81         } 82     } 83      84     func equiv(_ x:Int,_ y:Int) -> Bool 85     { 86         @H_@R_301_6940@_158@return root(x) == root(y) 87     } 88      89     func union(_ x:Int,_ y:Int) -> Bool 90     { 91         @H_@R_301_6940@_158@var x:Int = root(x) 92         @H_@R_301_6940@_158@var y:Int = root(y) 93         @H_@R_301_6940@_158@if x != y 94         { 95             @H_@R_301_6940@_158@if upper[y] < upper[x] 96             { 97                 @H_@R_301_6940@_158@var d:Int = x 98                 x = y 99                 y = d100             }101             upper[x] += upper[y]102             upper[y] = x103             w[x] += w[y]104         }105         @H_@R_301_6940@_158@return x == y106     }107     108     func count() -> Int109     {110         @H_@R_301_6940@_158@var ct:Int = 0111         @H_@R_301_6940@_158@for u @H_@R_301_6940@_158@in upper112         {113             @H_@R_301_6940@_158@if u < 0114             {115                 ct += 1116             }117         }118         @H_@R_301_6940@_158@return ct119     }120 }

总结

以上是内存溢出为你收集整理的[Swift Weekly Contest 113]LeetCode952. 按公因数计算最大组件大小 | Largest Component Size by Common Factor全部内容，希望文章能够帮你解决[Swift Weekly Contest 113]LeetCode952. 按公因数计算最大组件大小 | Largest Component Size by Common Factor所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。