Coursera Algorithms week1 查并集 练习测验:2 Union-find with specific canonical element
2024-08-23 14:53:25
题目原文:
Add a method find() to the union-find data type so that find(i) returns the largest element in the connected component containing i. The operations, union(), connected(), and find() should all take logarithmic time or better.
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class FindLargestUF {
private int[] id;
private int count;
public FindLargestUF(int n) {
count = n;
id = new int[n];
for (int i = 0; i < n; i++)
id[i] = i;
}
public int count(){
return count;
}
public boolean connected(int p, int q){
return (find(p)==find(q));
}
public int find(int p) {
while (p != id[p])
p = id[p];
return p;
} public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
StdOut.println("find("+p+")="+pRoot+",find("+q+")="+qRoot);
if (pRoot == qRoot)
return;
else if (pRoot < qRoot)
id[pRoot] = qRoot;
else
id[qRoot] = pRoot;
count--;
} public static void main(String[] args) {
int n = StdIn.readInt();
FindLargestUF uf = new FindLargestUF(n);
while (!StdIn.isEmpty()) {
int p = StdIn.readInt();
int q = StdIn.readInt();
if (uf.connected(p, q))
continue;
uf.union(p, q);
StdOut.println("link points:" + p + " " + q);
}
StdOut.println(uf.count() + "components");
}
}
For example, if one of the connected components is {1,2,6,9}, then the find() method should return 9 for each of the four elements in the connected components.
分析:
这一题很简单,要求find到的根是子集中的最大元素。因此只需要在union时,用两个子集中较大的root作为合并后的root就可以了。以下代码提交100
最新文章
- (十二)Maven生命周期和插件
- 用户名 不在 sudoers文件中
- Scala编程--函数式对象
- iOS开发零基础--Swift教程 可选类型
- oc面向对象特性: 多态
- Java8初体验(二)Stream语法详解
- OLAT &; OLTP
- RGui的http代理设置
- (剑指Offer)面试题16:反转链表
- json网页预览插件
- 启用Spring quartz定时器,导致tomcat服务器自动停止
- Entity FramWork - 在VS里面直接创建表,并同步到数据库
- SAP ABAP exporting list to memory ...SUBMIT 程序传输屏幕参数
- Redis客户端管理工具的安装及使用
- 【SqlServer系列】集合运算
- CentOS 7 如何设置默认启动方式为命令行模式
- 自己开发chrome插件生成二维码
- NYOJ 一笔画
- MVC杂记
- java⑧