java - 使用 TreeMap 查找最大元素

Question

我正在设计棒球联盟前 5 名击球手的记分牌。我正在使用 TreeMap，其中 player_name 作为 value，Player 作为 key。

Map<Player, String> players  = new TreeMap<>(Collections.reverseOrder());

Player 类别根据联赛得分进行自然排序 比较(this.leagueRuns, otherPlayer.leagueRuns)

leagueRuns 在比赛过程中不断更新，前 5 名击球手记分牌也会相应变化。下面是更新玩家联赛成绩并重新插入到 TreeMap 中的代码。更新后，将检索并显示 Map 中的 TOP 5 条目。

 public void updateRuns(String playerName, int runsScored) {

            Iterator<Entry<Player, String>> playersEntries = players.entrySet().iterator();

            Player player = null;
            while (playersEntries.hasNext()) {
                Entry<Player, String> currentPlayer = playersEntries.next();
                if (currentPlayer.getValue().equalsIgnoreCase(playerName)) {
                    player = currentPlayer.getKey();
                }
            }
            players.remove(player);
            player.addRuns(runsScored);
            players.put(player, player.getName());        
 }

一切正常，但我有以下担忧:

1. 为了对Player进行排序，我将其用作TreeMap中的Key。但必须遍历整个 Map 才能找到正在更新的 Player。因此时间复杂度从 O(1) 降到了 O(n)。更糟糕的是，我必须删除该 Player，更新它并重新插入，否则更改将不会生效。因此O(n + logn)。有没有一种方法可以按照自然顺序对 Player 进行排序，并且还能够在 O(1) 内进行搜索。我想重新插入是不可避免的。
2. 每次为玩家更新 leagueRuns 时，整个 TreeMap 都必须重新排序。您认为创建一个单独的前 5 名击球手的最小堆可以解决这个问题并且是一个可行的想法吗？
3. 有关设计或提高时间复杂度的任何技巧。

Answer 1

您应该支持 2 种结构:

1. 快速玩家搜索(名称 => 玩家)，例如HashMap<字符串，玩家>
2. 计分板的排序结构(玩家和得分)，例如TreeSet<玩家>

因此更新记分板的时间复杂度为 O(log(N)):

Map<String, Player> players;
SortedSet<Player> scoreboard;

public void updateRuns(String playerName, int runsScored) {
    Player player = players.get(playerName);
    if (player == null) {
        player = new Player(playerName, runsScored);
    } else {
        scorepoard.remove(player);
        player.addRuns(runsScored);
    }
    scoreboard.add(player);
}

如果您使 Player 类不可修改(首选方式)，您将获得相同的 O(log(N)):

public void updateRuns(String playerName, int runsScored) {
    Player player = players.remove(playerName);
    if (player == null) {
        player = new Player(playerName, runsScored);
    } else {
        scorepoard.remove(player);
        player = new Player(playerName, player.getRuns() + runsScored);
    }
    players.put(playerName, player);
    scoreboard.add(player);
}