关于并查集的一道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回答

liuyubobobo

2020-06-01

抱歉,你这样直接贴代码我无法帮你调试。我的使用并查集的参考代码,可以看看思路有没有可以借鉴的地方(C++):https://github.com/liuyubobobo/Play-Leetcode/blob/master/1202-Smallest-String-With-Swaps/cpp-1202/main2.cpp


继续加油!:)

0
11
厥~~~
非常感谢!
2020-09-03
共11条回复

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程