- 浏览: 787350 次
- 性别:
- 来自: 深圳
文章分类
最新评论
-
萨琳娜啊:
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 4676/** 二维数组 对角线输出 两个方向 例如对于数 ... -
bitmap求哈密顿距离-给定N(1<=N<=100000)个五维的点A(x1,x2,x3,x4,x5),求两个点X(x1,x2,x3,x4,x5)和Y(
2012-12-27 21:12 2954import java.util.Random; / ... -
百度笔试题:一个已经排序好的很大的数组,现在给它划分成m段,每段长度不定,段长最长为k,然后段内打乱顺序,请设计一个算法对其进行重新排序
2012-12-21 18:17 4102import java.util.Arrays; ... -
有一个数组,每次从中间随机取一个,然后放回去,当所有的元素都被取过,返回总共的取的次数。写一个函数实现。复杂度是什么。
2012-12-07 14:32 3604import java.util.Random; i ... -
单调队列-用一个长度为k的窗在整数数列上移动,求窗里面所包含的数的最大值
2012-11-11 22:32 2357import java.util.LinkedList; ... -
据说是2012年10月人人网校招的一道笔试题-给出一个重物重量为X,另外提供的小砝码重量分别为1,3,9。。。3^N。 将重物放到天平左侧,问在两边如何添加砝码
2012-10-28 23:41 1971public class ScalesBalance { ... -
java-拷贝特殊链表:有一个特殊的链表,其中每个节点不但有指向下一个节点的指针pNext,还有一个指向链表中任意节点的指针pRand,如何拷贝这个特殊链表?
2012-04-20 10:04 2981public class CopySpecialLinke ... -
java-写一函数f(a,b),它带有两个字符串参数并返回一串字符,该字符串只包含在两个串中都有的并按照在a中的顺序。
2012-04-17 19:50 3484public class CommonSubSeque ... -
java-同步访问一个数组Integer[10],生产者不断地往数组放入整数1000,数组满时等待;消费者不断地将数组里面的数置零,数组空时等待
2012-04-14 15:39 2321public class PC { /** ... -
java-两整数相除,求循环节
2012-04-14 13:52 4649import java.util.ArrayList; ... -
java-颠倒一个句子中的词的顺序。比如: I am a student颠倒后变成:student a am I
2012-04-14 10:27 3990public class ReverseWords { ... -
java-谷歌面试题-给定一个排序数组,如何构造一个二叉排序树
2012-04-12 11:10 4382import java.util.LinkedList; ... -
java-谷歌面试题-设计方便提取中数的数据结构
2012-04-12 10:10 2152网上找了一下这道题的解答,但都是提供思路,没有提供具体实现。其 ... -
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 3791这道题的具体思路请参看 何海涛的微博:http://weibo ... -
java-给定两个已排序序列,找出共同的元素。
2012-04-06 13:09 2862import java.util.ArrayList; ... -
java-谷歌面试题-给定一个固定长度的数组,将递增整数序列写入这个数组。当写到数组尾部时,返回数组开始重新写,并覆盖先前写过的数
2012-03-31 12:16 5022public class SearchInShifte ... -
java-13个坏人和13个好人站成一圈,数到7就从圈里面踢出一个来,要求把所有坏人都给踢出来,所有好人都留在圈里。请找出初始时坏人站的位置。
2012-03-28 22:13 1547import java.util.ArrayList; ... -
java-给定字符串,删除开始和结尾处的空格,并将中间的多个连续的空格合并成一个。
2012-03-26 10:59 7666public class DeleteExtraSpa ... -
java实现两个大数相加,可能存在溢出。
2012-03-25 11:08 6706import java.math.BigInteger; ... -
给定能随机生成整数1到5的函数,写出能随机生成整数1到7的函数
2012-03-21 22:15 3743import java.util.ArrayList; ...
相关推荐
这种数据结构常用于解决并查集问题,例如在图的连通性判断、Kruskal's最小生成树算法、Tarjan's强连通分量检测等场景。 ml-disjoint-set库提供了以下特性: 1. **快速查找**:通过路径压缩(Path Compression)...
数据结构中的并查集(Disjoint Set)是一种用于处理元素集合的分割问题的数据结构,它主要支持两种操作:合并(union)与查找(find)。在实际应用中,尤其是在算法竞赛(ACM)和图论中,它被广泛用于解决快速查询和...
在计算机科学领域,特别是数据结构的研究中,**Union-Find**(并查集)是一种用于处理一些不交集(Disjoint Sets)合并及查询问题的重要数据结构。这种数据结构能够高效地支持两种基本操作:查找(Find)和合并...
并查集(Disjoint Set)是一种树形的数据结构,常用于处理一些不交集的合并及查询问题,比如图中的连通分量、网络中的连通区域等。它支持两种基本操作:查找(Find)和合并(Union)。查找操作用于确定某个元素所在...
并查集(Disjoint Set Union, DSU)是一种用于处理一些不交集的合并及查询问题的数据结构。它主要用于解决元素集合的划分问题,能够高效地执行集合的合并和查询操作。 ##### 基本概念: - **集合的表示**:并查集...
7. **集合的并查集(Disjoint Set)**: - 并查集是一种高级集合操作,用于处理不相交集合的合并与查询。它包含“Find”(查找元素所属集合)和“Union”(合并两个集合)操作。C语言中可以通过路径压缩或按秩合并...
可以使用并查集(Disjoint Set)数据结构,它支持路径压缩和按秩合并,能有效减少查找和连接操作的时间复杂度。 2. 交集(Intersection):找出两个集合共有的元素。可以先对两个集合进行排序,然后使用两个指针...
代码部分展示了一个用C语言编写的程序,涉及到数据结构中的并查集(Disjoint Set)算法,这通常用于解决图中的连通性问题,如寻找最小生成树或解决集合的合并与查找问题。以下是对这一知识点的深入解析: ### 并查...
如果集合包含子集合且没有重复元素,使用广义表(Generalized List)或并查集(Disjoint-set)结构可以有效地存储和操作这些子集合。 对于全集合到特定整数范围的映射,例如: - (1) 整数0到99,可以使用一个大小...
不相交集(Disjoint Sets)是一种数据结构,用于维护一组元素,这些元素可以被分成多个互不相交的集合。在许多算法中,如Kruskal's最小生成树算法或Prim's算法,不相交集是核心组件之一。在这个场景下,我们使用Java...
并查集(Disjoint-Set)是处理不相交集合的数据结构,主要应用于寻找元素之间的连接关系,如图的连通性。它支持两个基本操作:“union”(合并两个集合)和“find”(查找元素所属的集合)。等价类是具有相同性质的...
接下来,可以采用并查集(Disjoint-Set)数据结构来高效地处理集合合并。并查集的主要操作包括find(查找元素所属集合的代表)和union(合并两个集合),这两个操作的时间复杂度都可以优化到近乎常数级别。在处理...
### 不相交集(Disjoint Set)与并查集 不相交集,也被称为并查集,是一种用于处理一些不相交集合合并及查询问题的数据结构。其核心操作包括查找(Find)和合并(Union),以及可选的压缩路径(Path Compression)...
算法复杂度为O(n^2),可以通过优化算法减少复杂度,例如使用并查集(Disjoint Set)数据结构。 2. 移动数字游戏: 这是一个经典的排列问题,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来解决。首先,...
- **MFSet类**:用于实现并查集(Disjoint Set),用来合并不同的顶点集合。该类包含了查找元素所属集合(Find_MFSet)和合并两个集合(Merge_MFSet)的方法。 #### 2. 关键函数解释 - **InputGraph()**:用于输入图的...
1. **并查集(Disjoint Set)**:是一种树形的数据结构,常用来处理一些不交集的合并及查询问题。本题中用来判断两个元素是否属于同一个集合(即是否属于同一个帮派)。 2. **并查集的基本操作**:包括查找(Find)...
- **并查集(Union-Find)**:一种用于处理不相交集动态变化的数据结构,支持查询某个元素所属集合的操作以及将两个集合合并成一个的操作。 #### 9. 图算法(Graph Algorithms) - **图(Graph)**:由顶点集合和边集合...
可以使用并查集(Disjoint Set)数据结构,对集合进行排序,然后依次合并小集合到大集合。算法复杂度是O(n log n),其中n是集合的数量。改进方向:利用字符串操作优化比较过程,减少不必要的比较。 以上五道题目都...
7. **不相交集算法(Disjoint Set)**:用于维护一组不相交集合的结构,支持快速的“连接”和“查询”操作,常见于并查集问题。 8. **图论算法**:包括遍历(深度优先搜索和广度优先搜索)、最短路径(Dijkstra算法...