優先級隊列 - 連續的整數組

我正在處理這個問題：將數字列表劃分爲連續數字組，但它們的原始順序應該保留？例如輸入：8,2,4,7,1,0,3,6 輸出：2,4,1,0,3和8,7,6優先級隊列 - 連續的整數組

予實現的溶液，簡單地說：

將原始數組存儲到映射中，其中鍵是輸入元素，值是它們在原始數組中的索引。
對輸入數組進行排序
檢查排序的數組，並在數字連續時將每個元素添加到優先級隊列中。

但是有一些錯誤PriorityQueue。例如，如果輸入是{2,4,3}，則PriorityQueue將最終爲{2,3,4}。我試圖調試它，我發現我的實現可以用兩個數字正常工作，但是當我添加第三個數字時，它只將自身與隊列頭部進行比較，所以3（原始索引2）從未進行過比較與4（原始索引1）。所以看起來，添加到這個隊列中的新對不會與其他所有元素進行比較。但是這不應該發生，所以我不確定問題是什麼，有人可以幫我看看我的代碼嗎？

public class ConsecutiveGroupsofIntegers { 

    public static void main(String[] args){ 
     List<Integer> input = Lists.newArrayList(2,4,3); 

     List<PriorityQueue<Pair<Integer, Integer>>> groups = findGroups(input); 

     for(PriorityQueue<Pair<Integer, Integer>> group : groups){ 
      for(Pair<Integer, Integer> pair : group){ 
       System.out.print(pair.getKey() + ","); 
      } 
      System.out.println("============"); 
     } 

    } 

    public static List<PriorityQueue<Pair<Integer, Integer>>> findGroups(List<Integer> input){ 

     Map<Integer, Integer> map = new LinkedHashMap<>(); 
     for(int i = 0; i < input.size(); i++){ 
      map.put(input.get(i), i); 
     } 

     Collections.sort(input); 
     List<PriorityQueue<Pair<Integer, Integer>>> groups = new ArrayList<>(); 
     PairComparator comparator = new PairComparator(); 
     PriorityQueue<Pair<Integer, Integer>> group = new PriorityQueue<>(input.size(),comparator); 
     int first = input.get(0); 
     group.add(new ImmutablePair<>(first, map.get(first))); 
     for(int i = 1; i < input.size(); i++){ 
      int num = input.get(i); 
      int index = map.get(num); 

      if(input.get(i) - input.get(i-1) > 1){ 
       groups.add(group); 
       group = new PriorityQueue<>(input.size(),comparator); 
      } 
      group.add(new ImmutablePair<>(num, index)); 

      if(i == input.size()-1){ 
       groups.add(group); 
      } 

     } 

     return groups; 
    } 

    public static class PairComparator implements Comparator<Pair<Integer, Integer>>{ 

     @Override 
     public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) { 
      return o1.getRight() - o2.getRight(); 
     } 
    } 

}

來源

2015-02-07 ggkiks

你的分組標準是什麼？ – 2015-02-07 05:29:39

@ I.K。每個組只包含連續的數字，所以我的分組標準是input.get（i） - input.get（i-1）<= 1。 – ggkiks 2015-02-07 05:31:05

除了打印方式，您的代碼看起來正確。 :-)

當您迭代優先級隊列時，不要期望它按您期望的順序給出元素。如果您需要按順序排列項目，則實際上應該使用.peek(..)或.poll(..)方法。

從Javadoc：

此類及其迭代器實現所有的 Collection和Iterator接口的所有可選方法。 方法迭代器（）中提供的迭代器不保證以任何特定順序遍歷優先級隊列的元素。如果你需要有序的遍歷，考慮使用Arrays.sort（pq.toArray（））。

對於穿越，你應該考慮轉換成一個列表後手動排序。對於一次性使用，您應該改爲：

while (!group.isEmpty()) { 
    System.out.print(group.poll().getKey() + ","); 
}

來源

2015-02-07 06:14:48 SuperSaiyan

非常感謝！它現在按照正確的順序打印。我不明白的是，當我調試它時，調試器中顯示的順序是錯誤的順序（當我嘗試在我的原始代碼中打印時，順序相同），但是當我做poll.getkey（）時，訂單是固定的。所以我的問題是爲什麼調試器中顯示的順序與實際順序（poll（））不同？謝謝 – ggkiks 2015-02-07 06:21:35

這是因爲即使您的調試程序與您顯示優先級隊列實例的內容所做的操作相同。 – SuperSaiyan 2015-02-07 12:27:55

如果您想要原始訂單，您需要使該比較器的一個小鍵。

來源

2015-02-07 09:19:24 EJP

您能解釋一下「比較器的小調」是什麼意思嗎？我認爲我實施比較器的方式應該提供足夠的信息來訂購。或者你的意思是像linkedhashmap？ – ggkiks 2015-02-07 17:38:18

優先級隊列 - 連續的整數組

回答

相關問題