-1

由于没有更好的名称，我将我正在寻找的数据结构称为“TopScoreMap”。这是要求。首先，地图的大小是固定的。例如，该地图只需要保留将在该地图上抛出的前 n 个条目。就其键而言，排在前 n 位。由于地图应按其键排序，因此我选择基于java.util.TreeMap. 以下是我已经实施的。这已经通过了一些测试用例。我的问题是：

  1. 是否存在提供此功能的现有数据结构？

  2. 如果没有，有没有办法在执行时避免迭代put？看起来像 O(n^2)，最坏的情况。

class TopScoreMap {
  TreeMap<Integer, String> map = new TreeMap<Integer, String>();
  int max = 0;

  public TopScoreMap() {
    this(5);
  }

  public TopScoreMap(int maxCapacity) {
    this.max = maxCapacity;
  }

  public void put(int score, String player) {
    if (map.size() < max) {
      map.put(score, player);
    }
    else {
      Iterator<Integer> it = map.keySet().iterator();
      while (it.hasNext()) {
        int currentKey = it.next();
        if (currentKey < score) {
          map.remove(currentKey);
          map.put(score, player);
          return;
        }
      }
    }
  }

}
4

3 回答 3

2

你可能想看看PriorityQueue，这样你就不需要迭代器了......但是如果它增长超过限制，你应该从最后删除元素

或者你应该使用SortedMap：

public class T1 {
    SortedMap<Integer, String>  m=new TreeMap<Integer, String>();
    void add(Integer i,String n){
        m.put(i,n);
        if(m.size()>3){
            m.tailMap(m.lastKey()).clear();
        }
        System.out.println(m);
    }
    public static void main(String[] args) {
        T1 t = new T1();
        t.add(1,"a");t.add(2,"b");t.add(3,"c");t.add(4,"d");t.add(0,"e");
    }
}
于 2013-09-03T20:43:34.527 回答
1

有了来自 SO 的输入，这就是我所做的（暂时不用担心同步）

class ScoreMap {
    SortedMap<Integer, String> map = new TreeMap<Integer, String>(Collections.reverseOrder());
    int max = 5;

    public ScoreMap(int maxCapacity) {
      this.max = maxCapacity;
    }

    public void put(int score, String player) {
      map.put(score, player);
      if (map.size() > max) {
        map.remove(map.lastKey());
      }
    }
    //....
}
于 2013-09-19T03:51:32.073 回答
1

您可以只查看底层 TreeMap 的 lastKey 而不是迭代器。如果新条目更大，则接受它。

就像是：

  int lastKey = map.getLastKey();
  if (lastKey < score) {
    map.remove(lastKey);
    map.put(score, player);      
  }
于 2013-09-03T20:55:12.600 回答