优先级队列的字符串排序问题(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]正确的顺序应该是: hello, hey, hi.

在我将数据结构改为TreeSet,并使用相同的比较器后,它就工作了。

解决方案:

你正在使用 ArrayList 构造者 从作为参数传递的集合中复制元素,然后调用 toArray 方法。对于 PriorityQueue 它只是对底层数组进行复制,而且这些元素没有特定的顺序。从 PriorityQueue::toArray docs :

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

然而对于一个 TreeSet::toArray 继承自 AbstractCollection):

返回一个包含该集合中所有元素的数组。如果这个集合对其迭代器返回元素的顺序做了任何保证,那么这个方法必须以相同的顺序返回元素。

而实际上 TreeSet 对它的迭代器返回的元素顺序进行担保。从 TreeSet::iterator docs :

以升序返回这个集合中元素的迭代器。

这就是为什么你会得到这样的结果。为了得到你想要的结果,你必须对你的队列进行轮询,以比较器定义的顺序来接收元素。

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 不返回元素i的顺序,但是对于 TreeSet 顺序是升序的(考虑到比较器)。

给TA打赏
共{{data.count}}人
人已打赏
未分类

迁移Cordova到Capacitor - 错误:包android.support.v4.content不存在[重复]。

2022-11-13 6:36:19

未分类

Django:没有这样的表

2022-11-13 6:36:21

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索