首页 / JAVA / 并差集 Java实现
并差集 Java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了并差集 Java实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含4596字,纯文字阅读大概需要7分钟。
内容图文
![并差集 Java实现](/upload/InfoBanner/zyjiaocheng/666/4cdec8d174134e38a8108e0e71fa748d.jpg)
关于并差集笔者也实在不想扯那么多理论,代码这个东西越扯理论越糊涂,自己实践才会知道要点在哪里。
一、并差集概念
并查集就分为两个操作一个并一个查,通常这种题都是分类的题,类间元素都是有关系的,类外元素没有关系。题目一定会给出两个元素之间的关系,这时我们就查find(),如果两个元素在一个集合里面就什么都不作;如果两个元素不在一个集合里,我们将这两个元素所在集合合并,因为这个集合里面的元素都是相互之间有关系的。所以这样的题目,找到元素之间存在的关系就是题眼,关系就是分类的依据。
二、并差集操作
1、双亲表示法
这里我们采用双亲表示法作为实现并差集的数据结构,双表示法即每个结点要记录自己的父结点。
并差集随不同的数据结构会有不同的实现,所以还是那句话思想最重要。
//使用双亲表示法作为存储结构 public class Node { public String data; public int parent; }
2、初始化
private Node[] ufs; UFoperation(String[] datas) { ufs = new Node[datas.length]; for(int i = 0; i < datas.length; i++) { ufs[i] = new Node(); ufs[i].data = datas[i]; ufs[i].parent = -1; } }
3、查操作
(1)常规查操作
int find(String data) { int pos = -1; for(int i = 0; i < ufs.length; i++) { if(ufs[i].data==data) { pos = i; break; } } while(ufs[pos].parent!=-1) { pos = ufs[pos].parent; } return pos; }
算法思想:就是找树的根节点啊
时间复杂度:O(h) h为树高
(2)带路径压缩的查操作
算法思想:我们每做一次查操作,就把待查结点以及其祖先结点(除根结点)都直接连在根结点之上,就是最终的树树高只有2,结点全部连到根结点上。
int find(String data) { int pos = -1; int mark = -1; int root = -1; int pre = -1; for(int i = 0; i < ufs.length; i++) { if(ufs[i].data==data) { pos = i; break; } } mark = pos; while(ufs[pos].parent!=-1) { pos = ufs[pos].parent; } root = pos; pos = mark; //这里根节点一定不可以进来,因为使用了前置指针,会下标出界。 while(ufs[pos].parent!=-1) { pre = ufs[pos].parent; ufs[pos].parent = root; pos = pre; } return root; }
时间复杂度:O(1)
4、并操作
算法思想:直接把一棵树根结点的父指针指向另一棵树的根结点
boolean merge(String s1, String s2) { int p1 = find(s1); int p2 = find(s2); if(p1==p2) return false; else { ufs[p2].parent = p1; return true; } }
时间复杂度:O(1)
完整代码:
![并差集 Java实现 - 文章图片](/upload/getfiles/0001/2021/5/2/20210502070304291.jpg)
![并差集 Java实现 - 文章图片](/upload/getfiles/0001/2021/5/2/20210502070304388.jpg)
public class UFoperation { private Node[] ufs; UFoperation(String[] datas) { ufs = new Node[datas.length]; for(int i = 0; i < datas.length; i++) { ufs[i] = new Node(); ufs[i].data = datas[i]; ufs[i].parent = -1; } } /*int find(String data) { int pos = -1; for(int i = 0; i < ufs.length; i++) { if(ufs[i].data==data) { pos = i; break; } } while(ufs[pos].parent!=-1) { pos = ufs[pos].parent; } return pos; }*/ //带路径压缩的 int find(String data) { int pos = -1; int mark = -1; int root = -1; int pre = -1; for(int i = 0; i < ufs.length; i++) { if(ufs[i].data==data) { pos = i; break; } } mark = pos; while(ufs[pos].parent!=-1) { pos = ufs[pos].parent; } root = pos; pos = mark; //这里根节点一定不可以进来,因为使用了前置指针,会下标出界。 while(ufs[pos].parent!=-1) { pre = ufs[pos].parent; ufs[pos].parent = root; pos = pre; } return root; } boolean merge(String s1, String s2) { int p1 = find(s1); int p2 = find(s2); if(p1==p2) return false; else { ufs[p2].parent = p1; return true; } } public static void main(String[] args) { String[] input = new String[] {"A","B","C","D","E","F","G","H","I"}; UFoperation u = new UFoperation(input); String[][] test = {{"A","B"},{"A","C"},{"D","E"},{"D","F"},{"D","G"},{"H","I"}}; for(int i = 0; i < test.length; i++) { u.merge(test[i][0],test[i][1]); } for(String s : input) { System.out.print(u.find(s) + " "); } } }View Code
5、带权路径
class Solution { private HashMap<String,String> SS = new HashMap<>(); private HashMap<String,Double> w = new HashMap<>();//记录到父节点的权值 public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) { init(equations); double[] ans = new double[queries.size()]; for(int i = 0; i < values.length; i++) { List<String> list = equations.get(i); merge(list.get(0),list.get(1),values[i]); } for(int i = 0; i < queries.size(); i++) { List<String> list = queries.get(i); if(find(list.get(1))==find(list.get(0))&&SS.containsKey(list.get(0))) ans[i] = getRootValue(list.get(1))/getRootValue(list.get(0)); else ans[i] = -1.0; } return ans; } private void init(List<List<String>> equations) { for(List<String> list : equations) { for(String s : list) { if(!SS.containsKey(s)) { SS.put(s,s); w.put(s,1.0); } } } } private String find(String s1) { while(SS.get(s1)!=s1) { s1 = SS.get(s1); } return s1; } //求到根节点的权值 private double getRootValue(String s) { double value = 1.0; while(SS.get(s)!=s) { value = value*(w.get(s)); s = SS.get(s); } return value; } private void merge(String s1, String s2, double value) { String p1 = find(s1); String p2 = find(s2); if(p1==p2) return; SS.put(p2,p1); w.put(p2,(getRootValue(s1)*value)/getRootValue(s2)); } }
像这样的题要在40钟之内完成还是有压力的鸭。
内容总结
以上是互联网集市为您收集整理的并差集 Java实现全部内容,希望文章能够帮你解决并差集 Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。