时间戳

首页 > 解决方案 > PriorityQueue (Java) 的字符串排序问题

java - PriorityQueue (Java) 的字符串排序问题

问题描述

我试图使用 PriorityQueue 对字符串列表进行排序并删除重复项。最初我使用 PriorityQueue，它不会改变顺序。在我更改为 TreeSet 后，它起作用了。但是，我想通过定义的比较器了解优先级队列的问题。很想听听一些解释。

不工作的代码：

public class RemoveDuplicateStrings {
    public static ArrayList<String> removeDuplicates(List<String> input) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> a.compareTo(b));

        for (String s : input) {
            if (!pq.contains(s)) {
                pq.add(s);
            }
        }
        return new ArrayList<String>(pq);
    }

    public static void main(String[] args) {
        List<String> output = removeDuplicates(List.of("Hey", "Hi", "Hello", "Hey", "Hello"));
        System.out.println(output);
    }
}

结果我得到： [Hello, Hi, Hey]，正确的顺序应该是：你好，嘿，嗨。

在我使用相同的比较器将数据结构更改为 TreeSet 后，它起作用了。

标签： javasortingcomparatorpriority-queue

解决方案

您正在使用ArrayList 构造函数，该构造函数从作为参数传递的集合中复制元素，并toArray在其上调用方法。因为PriorityQueue它只是制作底层数组的副本，并且这些元素没有特定的顺序。从PriorityQueue::toArray文档：

返回一个包含此队列中所有元素的数组。元素没有特定的顺序。

但是对于TreeSet::toArray（继承自的实现AbstractCollection）：

返回一个包含此集合中所有元素的数组。如果此集合对其迭代器返回其元素的顺序做出任何保证，则此方法必须以相同的顺序返回元素

实际上，TreeSet它保证了它的迭代器返回的元素的顺序。来自TreeSet::iterator文档：

按升序返回此 set 中元素的迭代器。

这就是为什么你会得到这样的结果。要获得您想要的内容，您必须轮询队列以按比较器定义的顺序接收元素：

public static ArrayList<String> removeDuplicates(List<String> input) {
        PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> a.compareTo(b));

        for (String s : input) {
            if (!pq.contains(s)) {
                pq.add(s);
            }
        }

        ArrayList<String> result = new ArrayList<>();
        while (!pq.isEmpty()) {
            result.add(pq.poll());
        }
        return result;
}

这里的关键是迭代器PriorityQueue不返回实际顺序的元素，但是TreeSet顺序是升序的（考虑到比较器）。

推荐阅读