Running time about 400ms, java solution, Using BFS and arrayList.


  • 0
    C
    public class Solution {
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
            if(node==null)return null;
            UndirectedGraphNode result=new UndirectedGraphNode(node.label);
            List<UndirectedGraphNode> nodes=new ArrayList<UndirectedGraphNode> ();
            List<UndirectedGraphNode> resultNodes=new ArrayList<UndirectedGraphNode> ();
            nodes.add(node);
            resultNodes.add(result);
            int n=0;
            while(n<nodes.size())
            {
                for(UndirectedGraphNode nd:nodes.get(n).neighbors)
                {
                    if(!nodes.contains(nd))
                    {
                        nodes.add(nd);
                        UndirectedGraphNode t=new UndirectedGraphNode(nd.label);
                        resultNodes.add(t);
                    }
                    resultNodes.get(n).neighbors.add(resultNodes.get(nodes.indexOf(nd)));
                }
                 n++;   
            } 
                return result;   
        }
    }

  • 1
    R

    nodes.contains() operation in your solution will take O(n) time. If you are looking for time optimization, use a HashSet to keep track of the visited nodes. It will tax the memory but will be faster.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.