优先队列 - 连续的整数组

Question

我正在研究这个问题：将数字列表分成一组连续的数字，但应保留它们的原始顺序？例如输入：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 个数字时，它只将自己与队列的头部进行比较，因此从未比较过 3（原始索引 2）有 4（原始索引 1）。因此，似乎没有将添加到该队列的新 Pair 与其他所有元素进行比较。但这不应该发生，所以我不太确定问题出在哪里，有人可以帮我看看我的代码吗？

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();
        }
    }

}

Answer 1

除了打印方式外，您的代码看起来是正确的。 :-)

当您遍历优先级队列时，不要指望它会按照您期望的顺序为您提供元素。如果您需要按顺序排列项目，您实际上应该使用 .peek(..) 或 .poll(..) 方法。

来自Javadoc：

This class and its iterator implement all of the optional methods of the Collection and Iterator interfaces. The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

对于遍历，你应该考虑转换为列表后手动排序。对于一次性使用，您应该改为：

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

Answer 2

如果你想要原来的顺序，你需要把它作为比较器的次键。

优先队列 - 连续的整数组

Priority Queue - Consecutive Groups of Integers

java

priority-queue