关于并查集的一道leetcode1202超时
来源:11-7 更多和并查集相关的话题
厥~~~
2020-05-31
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
class Solution {
int[] parent;
int[] rank;
public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
int len=s.length();
parent=new int[len];
rank=new int[len];
for (int i = 0; i < len; i++) {
parent[i]=i;
rank[i]=1;
}
for (List<Integer> list : pairs) {
union(list.get(0),list.get(1));
}
HashMap<Integer,List<Integer>> map= new HashMap<Integer, List<Integer>>();
for (int i = 0; i < len; i++) {
int p=find(i);
if (map.containsKey(p))map.get(p).add(i);
else {
List<Integer> l=new LinkedList<Integer>();
l.add(i);
map.put(p, l);
}
}
StringBuilder sb=new StringBuilder(s);
for (List<Integer> list : map.values()) {
char[] str= new char[list.size()];
for (int i = 0; i < list.size(); i++) {
str[i]=s.charAt(list.get(i));
}
Arrays.sort(str);
for (int i = 0; i < list.size(); i++) {
sb.setCharAt(list.get(i),str[i]);
}
}
return sb.toString();
}
public boolean isConnected(int p,int q) {
return find(p)==find(q);
}
public int find(int p) {
while(p!=parent[p]) {
parent[p]=parent[parent[p]];
p=parent[p];
}
return p;
}
public void union(int p,int q) {
int rootq=find(q);
int rootp=find(p);
if(rootq==rootp) return;
if (rank[rootp]<rank[rootq]) {
parent[rootp]=rootq;
}
else if(rank[rootq]<rank[rootp]) {
parent[rootq]=rootp;
}
else {
parent[rootq]=rootp;
rank[rootp]++;
}
}
}
老师为啥我这个会超时能,能通过35/36,最后一个通不过,哪里出问题了呢,需要怎么修改?
1回答
-
抱歉,你这样直接贴代码我无法帮你调试。我的使用并查集的参考代码,可以看看思路有没有可以借鉴的地方(C++):https://github.com/liuyubobobo/Play-Leetcode/blob/master/1202-Smallest-String-With-Swaps/cpp-1202/main2.cpp
继续加油!:)
0112020-09-03
相似问题