快速拓扑排序，当节点顺序显着时？

我正在做关于Hackerrank的this problem。问题摘要如下：快速拓扑排序，当节点顺序显着时？

您正在尝试重构范围[1,10^6]中M个不同整数的序列。您得到长度为2的子序列= N < = 10^3个子序列2 < = K < = 10^3。如果有两个序列是可能的，则返回按字典顺序较小的序列。

我的算法如下：

为每个不同的整数创建一个顶点。将它们存储在哈希映射中。
对于每一行，如果i在该行之前出现j，则将i的边添加到j。跟踪每个顶点的indegree。
建立优先队列，其关键是每个顶点的值。入队所有的顶点为indegree 0.
虽然队列非空：弹出顶部顶点。减少每个孩子的学习成绩。

我的答案是正确的，但是我在较大的测试用例上得到了超出时间限制。我认为优先级队列是瓶颈，但我想不出一种方法来使按值排序的顶点小于O(log n)。我的代码如下，与顶点类排除以保持较短的---它大多只是getter和setter方法：

class FavoriteSequence { 
    private Map<Integer, Vertex> seen; 

    public void solve(int testNumber, Scanner in, PrintWriter out) { 
     int numRows = in.nextInt(); 
     seen = new HashMap<>(); 

     for (int i = 0; i < numRows; i++) { 
      int numInRow = in.nextInt(); 
      List<Vertex> row = IntStream.range(0, numInRow).mapToObj(x -> getVert(in.nextInt())).collect(
        Collectors.toList()); 

      int idx = 0; 
      for (Vertex v : row) { 
       v.incInDegree(idx); 
       v.addChildren(row.subList(++idx, numInRow)); 
      } 
     } 

     List<String> ans = new LinkedList<>(); 
     Queue<Vertex> bfsQ = new PriorityQueue<>(new Comparator<Vertex>() { 
      public int compare(Vertex o1, Vertex o2) { 
       int valCmp = Integer.compare(o1.getValue(), o2.getValue()); 
       return valCmp; 
      } 
     }); 

     bfsQ.addAll(seen.values().stream().filter(c -> c.getInDegree() == 0).collect(Collectors.toList())); 

     while (!bfsQ.isEmpty()) { 
      Vertex me = bfsQ.poll(); 
      ans.add(Integer.toString(me.getValue())); 

      for (List<Vertex> cs : me.getChildrens()) { 
       for (Vertex c : cs) { 
        if (c.decInDegree() == 0) { 
         bfsQ.add(c); 
        } 
       } 
      } 
     } 

     out.println(String.join(" ", ans)); 
    } 

    private Vertex getVert(int idx) { 
     Vertex me = seen.get(idx); 

     if (me == null) { 
      me = new Vertex(idx); 
      seen.put(idx, me); 
     } 

     return me; 
    } 
}

我在做什么太慢？为了使它具体化，我提供了我的代码，但我真的在寻找算法的答案。

来源

2015-02-05 Patrick Collins

如果我没有记错的话，这个代码

 int idx = 0; 
     for (Vertex v : row) { 
      v.incInDegree(idx); 
      v.addChildren(row.subList(++idx, numInRow)); 
     }

增加了圆弧，其数量与子序列的长度平方增长。实际上只需要在传递约简中添加弧，即从子序列的每个元素到其直接后继。

来源

2015-02-05 20:07:53

如何在不进行拓扑排序的情况下判断一个元素是否是另一个元素的直接继承者？不能保证子序列中的元素在原始序列中彼此相邻。 – 2015-02-05 20:19:15

啊，我明白了。从顶点到第一个孩子的边缘足以强制排序，因为排序“X出现在Y之前”是可传递的。谢谢！ – 2015-02-05 20:31:46

快速拓扑排序，当节点顺序显着时？

回答

相关问题