如何在Java中使用允许重复的TreeSet？

-3

我想在O（LOGN）的时间与优先级队列功能的数据结构，还能够删除一定不是在O（LOGN）时间的头一个特定的元素。我听说java中的TreeSet做了它，但不允许重复，我如何解决这个问题？如何在Java中使用允许重复的TreeSet？

来源

2017-05-08 simha srivatsa

例如，你可以添加一个正在运行的ID，以确保您有没有重复 –

一组的*整点*，Java或其他地方，是它不允许重复。 – chrylis

如果你想插入重复的东西，然后创建一个数据结构并插入它的对象。这样它允许重复 – bharath

使用TreeMap它允许插入在log n时间和删除log n时间。您可以在那里存储TreeMap<Integer,Integer>其中密钥存储元素的值，值存储元素的频率。

如果你需要做的只是Insert和Delete操作，使用Java的Priority Queue。它也允许在log n时间插入和删除在log n时间，因为它使用Heaps来存储数据。

通过执行TreeMap的功能，您可以执行Insertion，Deletion。

TreeMap<Integer,Integer> map=new TreeMap<Integer,Integer>();

插入：

public boolean insert(int value) throws Exception 
{ 
    try 
    { 
     if(!map.containsKey(value)) 
      map.put(value,0); 

     map.put(value,map.get(value)+1); 

     return true; 
    } 
    catch(Exception e) 
    { 
     e.printStackTrace(); 
     return false; 
    } 
}

头队列（PEEK）：

public int getHead() 
{ 
    if(map.firstKey()==null) 
     return null; 

    return (int)map.firstKey(); 
}

删除和检索头（轮询）：

public int removeHead() 
{ 
    if(getHead()==null) 
     return null; 

    int head=getHead(); 

    if(map.get(head)==1) 
     map.remove(head); 
    else 
     map.put(head,map.get(head)-1); 
}

来源

2017-05-08 15:10:10

我没有足够的信誉发表评论，所以我会在这里说这个。我认为按照here的说明去除优先队列中的元素是O（N）。

你也许能够解决这个问题在某些情况下。如果您不打算在删除对象后添加对象，则可以对priorityqueue进行封装并保留已删除元素的散列集。然后，如果您在轮询时遇到该对象，则将其丢弃。

你也可以使用一个有序列表创建自己的PriorityQueue。然后，您可以使用二进制搜索来查找插入位置或要有效删除的索引。

来源

2017-05-08 15:28:38

如何在Java中使用允许重复的TreeSet？

回答

相关问题