带比较器的java优先级队列

chhkpiq4 于 2021-08-20 发布在 Java

关注(0)|答案(1)|浏览(378)

我使用优先级队列存储identity hashmap的元素（以便保留重复的密钥）。我想在优先级队列中根据键按降序添加identityhashmap元素，并打印它们的索引（从1开始）。但它没有给出正确的输出。
这是我的代码：

import java.util.*;
import java.lang.*;

class Test {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        IdentityHashMap<Integer, Integer> hm = new IdentityHashMap<>();
        PriorityQueue<Map.Entry<Integer, Integer>> p = new PriorityQueue<>(new my_Comparator());
        int size = sc.nextInt();
        int a[] = new int[size];
        for (int index = 0; index < size; index++) {
            a[index] = sc.nextInt();
            hm.put(a[index], index + 1);
        }
        for (Map.Entry<Integer, Integer> temp : hm.entrySet()) {
            p.add(temp);
        }
        while (p.size() != 0) {
            Map.Entry<Integer, Integer> temp = p.poll();
            System.out.print(temp.getValue() + " ");
        }
        System.out.println();
    }
}

class my_Comparator implements Comparator<Map.Entry<Integer, Integer>> {

    public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
        Integer i1 = o1.getKey();
        Integer i2 = o2.getKey();
        if (i1.equals(i2)) {
            return o2.getValue().compareTo(o1.getValue());
        }
        return i2.compareTo(i1);
    }
}

输入：

8
19 1 8 25 20 12 4 25

正确的输出如下：

8 4 5 1 6 3 7 2

这些是在优先级队列中按降序排序后的元素索引。
我的代码的输出是：

8 5 1 6 3 7 2

Java HashMap sorting Comparator priority-queue

来源：https://stackoverflow.com/questions/68306896/priority-queue-with-comparator

1条答案

按热度按时间

lp0sw83n1#

问题的出现是因为您试图在输入中使用重复的值。

for (int index = 0; index < size; index++) {
          a[index] = sc.nextInt();
          hm.put(a[index], index + 1);
      }

第一次输入25时，它会保存25的值和输入该值的索引。当最后再次输入25时，它会更新index.hashmap.put的值，如果键已经存在，则基本上会更新该值。因此，在原始hashmap中，只有7个条目存在。
要解决您的问题，请使用索引作为键，并将当前值作为hashmap的值。然后，当输入25时，它将存储这两个条目。这是给出所需输出的工作代码

import java.util.*;
import java.lang.*;
import java.io.*;

public class Test{
public static void main (String[] args) {

Scanner sc=new Scanner(System.in);
IdentityHashMap<Integer,Integer> hm=new IdentityHashMap<>();
PriorityQueue<Map.Entry<Integer,Integer>>p=new PriorityQueue<>(new myComparator());
    int size=sc.nextInt();
    int a[]=new int[size];
for(int index=0;index<size;index++)
{
    a[index]=sc.nextInt();
    hm.put(index+1,a[index]);
}
//System.out.println(hm);
for(Map.Entry<Integer,Integer> temp:hm.entrySet())
{
    p.add(temp);
}
while(p.size()!=0)
{Map.Entry<Integer,Integer>temp=p.poll();
    System.out.print(  temp.getKey() + " ") ;

}
System.out.println();
}       

}
class myComparator implements Comparator<Map.Entry<Integer,Integer>>
{

    public int compare(Map.Entry<Integer,Integer>o1,Map.Entry<Integer,Integer> o2)
    {
    Integer i1 =o1.getValue();
    Integer i2 =o2.getValue();
    if(i1.equals(i2))
    {
         return o2.getValue().compareTo(o1.getValue());

    }

     return i2.compareTo(i1);

    }

}

赞(0）回复(0）举报 2021-08-20

我来回答

带比较器的java优先级队列

1条答案

相关问题

热门标签

最新问答