• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode952.按公因数计算最大组件大小|LargestComponentSizebyCommonFactor ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

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,6,7,4,12,21,39]
Output: 8

Note:

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

给定一个由不同正整数的组成的非空数组 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

2676 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 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode752.打开转盘锁|OpentheLock发布时间:2022-07-13
下一篇:
Swift(二)控制流发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap