- 浏览: 777739 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
萨琳娜啊:
Java读源码之Netty深入剖析网盘地址:https://p ...
Netty源码学习-FileRegion -
飞天奔月:
写得有趣 ^_^
那一年你定义了一个接口 -
GoldRoger:
第二个方法很好
java-判断一个自然数是否是某个数的平方。当然不能使用开方运算 -
bylijinnan:
<script>alert("close ...
自己动手实现Java Validation -
paul920531:
39行有个bug:"int j=new Random ...
java-蓄水池抽样-要求从N个元素中随机的抽取k个元素,其中N无法确定
import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.Set; public class DisjointSet { /** 题目:给定一个字符串的集合,格式如:{aaa bbb ccc}, {bbb ddd},{eee fff},{ggg},{ddd hhh}要求将其中交集不为空的集合合并,要求合并完成后的集合之间无交集,例如上例应输出{aaa bbb ccc ddd hhh},{eee fff}, {ggg}。 (1)请描述你解决这个问题的思路; (2)请给出主要的处理流程,算法,以及算法的复杂度 (3)请描述可能的改进。 解答: 1. 假定每个集合编号为0,1,2,3... 2. 创建一个hash_map,key为字符串,value为一个链表,链表节点为字符串所在集合的编号。遍历所有的集合,将字符串和对应的集合编号插入到hash_map中去。 3. 创建一个长度等于集合个数的int数组,表示集合间的合并关系。例如,下标为5的元素值为3,表示将下标为5的集合合并到下标为3的集合中去。开始时将所有值都初始化为-1,表示集合间没有互相合并。在集合合并的过程中,我们将所有的字符串都合并到编号较小的集合中去。 遍历第二步中生成的hash_map,对于每个value中的链表,首先找到最小的集合编号(有些集合已经被合并过,需要顺着合并关系数组找到合并后的集合编号),然后将链表中所有编号的集合都合并到编号最小的集合中(通过更改合并关系数组)。 4.现在合并关系数组中值为-1的集合即为最终的集合,它的元素来源于所有直接或间接指向它的集合。 0: {aaa bbb ccc} 1: {bbb ddd} 2: {eee fff} 3: {ggg} 4: {ddd hhh} 生成的hash_map,和处理完每个值后的合并关系数组分别为 aaa: 0 [-1, -1, -1, -1, -1] bbb: 0, 1 [-1, 0, -1, -1, -1] ccc: 0 [-1, 0, -1, -1, -1] ddd: 1, 4 [-1, 0, -1, -1, 0] eee: 2 [-1, 0, -1, -1, 0] fff: 2 [-1, 0, -1, -1, 0] ggg: 3 [-1, 0, -1, -1, 0] hhh: 4 [-1, 0, -1, -1, 0] 所以合并完后有三个集合,第0,1,4个集合合并到了一起, 第2,3个集合没有进行合并。 Use "Disjoin-set".But I use "HashSet" and "HashMap" of Java API.Does "Disjoin-set" have its own data structure? see also [url]http://www.csie.ntnu.edu.tw/~u91029/DisjointSets.html[/url] */ private final int SIZE=7; private int[] father;//the root in disjion set. private static List<Set<String>> resultList=new ArrayList<Set<String>>(); public static void main(String[] args) { String[] str0={ "aaa", "bbb", "ccc",}; String[] str1={ "bbb", "ddd",}; String[] str2={ "eee", "fff",}; String[] str3={ "ggg",}; String[] str4={ "ddd", "hhh",}; String[] str5={ "xx", "yy",}; String[] str6={ "zz", "yy",}; String[][] strs={str0,str1,str2,str3,str4,str5,str6}; //change String[][] to List<Set> for(String[] str:strs){ //when I write--"Arraylist list=Arrays.asList(strArray)","addAll()" is unsupported for such a arraylist. Set<String> set=new HashSet<String>(); set.addAll(Arrays.asList(str)); resultList.add(set); } DisjointSet disjointSet=new DisjointSet(); disjointSet.disjoin(strs); } public void disjoin(String[][] strings){ if(strings==null||strings.length<2)return; initial(); Map<String,List<Integer>> map=storeInHashMap(strings); union(map); } //in the beginning,each element is in its own "group". public void initial(){ father=new int[SIZE]; for(int i=0;i<SIZE;i++){ father[i]=i; } } /*Map<k,v> * key:String * value:List<Integer>-in which sets the string shows up. */ public Map<String,List<Integer>> storeInHashMap(String[][] strings){ Map<String,List<Integer>> map=new HashMap<String,List<Integer>>(); for(int i=0;i<SIZE;i++){ for(String each:strings[i]){ if(!map.containsKey(each)){ List<Integer> list=new ArrayList<Integer>(); list.add(i); map.put(each, list); }else{ map.get(each).add(i); } } } //traverse the hashmap Iterator<Map.Entry<String, List<Integer>>> it=map.entrySet().iterator(); while(it.hasNext()){ Map.Entry<String, List<Integer>> entry=it.next(); String key=entry.getKey(); List<Integer> value=entry.getValue(); System.out.println(key+":"+value); } return map; } public void union(Map<String,List<Integer>> map){ Iterator<Map.Entry<String, List<Integer>>> it=map.entrySet().iterator(); while(it.hasNext()){ Map.Entry<String, List<Integer>> entry=it.next(); List<Integer> value=entry.getValue(); unionHelp(value);//the arrays whose indexes are in the same list should be merged to one set. } System.out.println("the father array is "+Arrays.toString(father)); //merge two sets for(int i=0;i<SIZE;i++){ if(i!=father[i]){ Set<String> dest=resultList.get(father[i]); Set<String> source=resultList.get(i); dest.addAll(source); } } //clear a set which has been added. for(int i=0;i<SIZE;i++){ if(i!=father[i]){ resultList.get(i).clear(); } } System.out.println("after merge:"+resultList); } public void unionHelp(List<Integer> list){ int minFather=getFather(list.get(0));//list[0] is the smaller. for(int i=0,size=list.size();i<size;i++){ father[list.get(i)]=minFather; } } //general union in disjoin set.But we overload it in this case. public void unionHelp(int x,int y){ if(father[x]!=father[y]){ int fx=getFather(x); int fy=getFather(y); //merge two arrays to the array that has a smaller index. if(fx<fy){ father[y]=fx; }else{ father[x]=fy; } } } public int getFather(int x){ while(x!=father[x]){ x=father[x]; } return x; } }
评论
2 楼
zzy88825
2013-04-16
第153行需要改为father[getFather(list.get(i))] = minFather;
不然这种[[aaa, ccc, bbb], [ddd, bbb], [fff, eee], [hhh], [hhh, ddd], [yy, xx], [zz, yy]]情况也会处理错误
不然这种[[aaa, ccc, bbb], [ddd, bbb], [fff, eee], [hhh], [hhh, ddd], [yy, xx], [zz, yy]]情况也会处理错误
1 楼
zzy88825
2013-04-16
第136行的Set<String> dest=resultList.get(father[i]); 不对
应该是Set<String> dest=resultList.get(getFather(i)); 不然算出的结果是错误的
应该是Set<String> dest=resultList.get(getFather(i)); 不然算出的结果是错误的
发表评论
-
二维数组(矩阵)对角线输出
2014-04-28 17:55 4595/** 二维数组 对角线输出 两个方向 例如对于数 ... -
bitmap求哈密顿距离-给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(
2012-12-27 21:12 2883import java.util.Random; / ... -
百度笔试题:一个已经排序好的很大的数组,现在给它划分成m段,每段长度不定,段长最长为k,然后段内打乱顺序,请设计一个算法对其进行重新排序
2012-12-21 18:17 4048import java.util.Arrays; ... -
有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。写一个函数实现。复杂度是什么。
2012-12-07 14:32 3543import java.util.Random; i ... -
单调队列-用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值
2012-11-11 22:32 2297import java.util.LinkedList; ... -
据说是2012年10月人人网校招的一道笔试题-给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 将重物放到天平左侧,问在两边如何添加砝码
2012-10-28 23:41 1916public class ScalesBalance { ... -
java-拷贝特殊链表:有一个特殊的链表,其中每个节点不但有指向下一个节点的指针pNext,还有一个指向链表中任意节点的指针pRand,如何拷贝这个特殊链表?
2012-04-20 10:04 2941public class CopySpecialLinke ... -
java-写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。
2012-04-17 19:50 3446public class CommonSubSeque ... -
java-同步访问一个数组Integer[10],生产者不断地往数组放入整数1000,数组满时等待;消费者不断地将数组里面的数置零,数组空时等待
2012-04-14 15:39 2294public class PC { /** ... -
java-两整数相除,求循环节
2012-04-14 13:52 4596import java.util.ArrayList; ... -
java-颠倒一个句子中的词的顺序。比如: I am a student颠倒后变成:student a am I
2012-04-14 10:27 3936public class ReverseWords { ... -
java-谷歌面试题-给定一个排序数组,如何构造一个二叉排序树
2012-04-12 11:10 4336import java.util.LinkedList; ... -
java-谷歌面试题-设计方便提取中数的数据结构
2012-04-12 10:10 2101网上找了一下这道题的解答,但都是提供思路,没有提供具体实现。其 ... -
java-腾讯暑期实习生-输入一个数组A[1,2,...n],求输入B,使得数组B中的第i个数字B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]
2012-04-08 23:10 3758这道题的具体思路请参看 何海涛的微博:http://weibo ... -
java-给定两个已排序序列,找出共同的元素。
2012-04-06 13:09 2828import java.util.ArrayList; ... -
java-谷歌面试题-给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数
2012-03-31 12:16 4981public class SearchInShifte ... -
java-13个坏人和13个好人站成一圈,数到7就从圈里面踢出一个来,要求把所有坏人都给踢出来,所有好人都留在圈里。请找出初始时坏人站的位置。
2012-03-28 22:13 1502import java.util.ArrayList; ... -
java-给定字符串,删除开始和结尾处的空格,并将中间的多个连续的空格合并成一个。
2012-03-26 10:59 7615public class DeleteExtraSpa ... -
java实现两个大数相加,可能存在溢出。
2012-03-25 11:08 6654import java.math.BigInteger; ... -
给定能随机生成整数1到5的函数,写出能随机生成整数1到7的函数
2012-03-21 22:15 3695import java.util.ArrayList; ...
相关推荐
分离集合(disjoint set)是一种经典的数据结构,它有三类操作: Make-set(a):生成包含一个元素a的集合S; Union(X, Y):合并两个集合X和Y; Find-set(a):查找元素a所在集合S,即通过元素找集合句柄;
并查集是一种树型的数据结构,用于处理一些不相交集合的合并问题。 并查集的主要操作有 1-合并两个不相交集合 2-判断两个元素是否属于同一个集合 3-路径压缩
Linked-List Implementation of Disjoint Set
前端开源库-ml-disjoint-setML不相交集,高效的不相交集数据结构实现
并查集(Disjoint Set)是一种用于处理集合合并和查询连通性的数据结构。它主要支持以下两种操作: MakeSet(x): 创建一个新的集合,其中包含元素x,并将其作为单独的集合。 Find(x): 查找元素x所属的集合的代表元素...
并查集(Disjoint-Set Union,简称DSU)是一种用于处理集合合并和查询问题的数据结构。它主要支持两种操作:查找(Find)和合并(Union)。并查集通常被用于解决一些图论、网络连接和集合类的算法问题。 ### 主要...
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复...
不相交集 Java 数据结构实现 用法 org.nnsoft.trudeau.collections.disjointset.DisjointSet是一个泛型友好的数据结构,它提供E find( E e )和void union( E e1, E e2 ) 。
Union-Find: A Data Structure for Disjoint Set Operations
pip install disjoint-set 您可以通过运行以下命令来验证您正在运行最新的软件包版本: >> > import disjoint_set >> > disjoint_set . __version__ '0.7.1' 用法 >> > from disjoint_set import DisjointSet >> > ...
并查集 并查集(Disjoint Set)是一种树型的数据结构,主要用于处理一些不相交集合(disjoint sets)的合并及查询问题。并查集的设计思路是在开始时,每个元素构成一个单元素的集合,然后按照一定顺序将属于同一组的...
ACM disjoint set
并查集实现,带路径压缩和template,高效查找神器!注:库里面如果没有unordered_map,可以换成hash_map或者map
不相交集数据结构是一种数据结构,它跟踪划分为多个不相交(非重叠)子集的一组元素。联合查找算法是对此类数据结构执行两个有用操作的算法: 查找:确定特定元素所在的子集。这可用于确定两个元素是否在同一子集中...
并查集(Union-Find)是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。 并查集存在两个操作(1.Union 联合 2.finddeputy 查找代表结点) 和一个需要解答的问题( issameset 是否 ...
var unionFind = new DisjointSet ( nodes ); // check intersections between scopes of given objects unionFind . Find ( Node1 , Node2 ) // union scopes unionFind . Union ( Node1 , Node2 ) 执照
[麻省理工学院-算法导论].Introduction.to.Algorithms.-.Lecture.Notes
并查集 Disjoint-Set-Union 最大流Edmonds-Karp算法 Edmonds-Karp 欧拉函数 Euler's-Totient-Function 有向图的欧拉回路 Eulerian-Tour(Digraph) 拓展欧几里得算法 Extended-Euclid 简单的快速幂 Fast-...
Disjoint-Sets-using-Union-Find:使用联合查找和树进行路径压缩的不相交集
资源分类:Python库 所属语言:Python 资源全名:disjoint_union-0.2.0-py2.py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059