java - 用Java更新游戏记录

Question

我们的游戏记录整理如下:

允许玩家玩不同级别的游戏，并保留一个高分表以显示游戏记录的前 10 名。高分表中的每条游戏记录都包含一组属性，例如玩家的姓名、获得的总分以及获得分数的级别。游戏战绩列表一般按照分数从高到低排序，表示玩家级别从高到低的排名。

我们必须实现

 public GameRecord[] updateGameRecords(GameRecord[] oldRecords, GameRecord newRecord)

通过以下方式:

1. 如果存在与 newRecord 具有相同名称和相同级别的记录，那么如果 newRecord 具有更高的分数，我们将更新该记录，然后我们对 oldRecords 进行排序并返回它。否则，转到步骤 2

2. 如果与newRecord同级别的记录数小于10，则将新记录插入oldRecords中排序后返回，否则转到第 3 步。

3. 如果在与 newRecord 相同的级别有任何得分较差的记录，那么我们将替换该级别得分最低的记录，因为给定级别的记录数不能超过 10，然后我们排序并返回 oldRecords .

到目前为止，这是我的代码:

public GameRecord[] updateGameRecords(GameRecord[] oldRecords, GameRecord newRecord) {
    int index = -1, r = 0;
    boolean break_loop = false, same_name_level = false;
    for (int i = 0; i < oldRecords.length; ++i) {
        while (i < oldRecords.length && newRecord.getLevel() < oldRecords[i].getLevel()) {
            ++i;
            continue;
        }
        while (i < oldRecords.length && i < oldRecords.length && newRecord.getLevel() == oldRecords[i].getLevel()) {
            if (r == 0)
                index = i;
            ++r;//r is number of records with same level
            if (!break_loop && newRecord.getName().equals(oldRecords[i].getName())) {
                same_name_level = true;
                break_loop = true;
                if (newRecord.getScore() > oldRecords[i].getScore()) {
                    oldRecords[i].setScore(newRecord.getScore());
                }
            }
            ++i;
        }
        if (break_loop == true)
            break;
    }

    if (break_loop == true) {
        Util.sort(oldRecords);
        return oldRecords;
    }

    if (r > 0 && r < 10 && same_name_level == false) {
        GameRecord[] temp = oldRecords.clone();
        oldRecords = new GameRecord[oldRecords.length + 1];
        System.arraycopy(temp, 0, oldRecords, 0, temp.length);
        oldRecords[temp.length] = newRecord;
        Util.sort(oldRecords);
        return oldRecords;
    }

    if (r == 10) {
        if (oldRecords[index + 9].getScore() < newRecord.getScore())
            oldRecords[index + 9].setScore(newRecord.getScore());
        Util.sort(oldRecords);
        return oldRecords;
    }

    if (r == 0) {
        GameRecord[] temp = oldRecords.clone();
        oldRecords = new GameRecord[oldRecords.length + 1];
        System.arraycopy(temp, 0, oldRecords, 0, temp.length);
        oldRecords[temp.length] = newRecord;
        Util.sort(oldRecords);
        return oldRecords;
    } else
        return oldRecords;
}

它工作正常，但这是线性时间复杂度代码，它需要 O( oldRecords.length ) + Util.sort() 花费的时间 函数，这使得总运行时间非线性.

你能给我推荐一个线性时间算法吗。

Answer 1

为了在插入或更新记录时维护一个排序列表，没有必要再次对整个列表进行排序；将此记录移动到适当的位置就足够了。而且，因为我们从不改变级别，只增加分数，所以我们知道这个记录只会向上移动。

也就是说，在您完成插入或更新记录后，我将调用以下方法:

void moveToProperPlace(GameRecord[] records, int index) {
    int newIndex = findCorrectIndex(records, index);
    if (newIndex != index) {
        GameRecord record = records[index];
        System.arrayCopy(records, newIndex, records, newIndex + 1, index - newIndex);
        records[newIndex] = record;
    }
}

int findCorrectIndex(records, index) {
    int i = index;
    do {
        i--;
    } while (i >= 0 && higher(records[index], records[i]);
    return i + 1;
}

boolean higher(GameRecord x, GameRecord y) {
    return x.getScore() > y.getScore() || (x.getScore() == y.getScore && x.getLevel() > y.getLevel());
}

由于预排序数据非常普遍，如果标准库中设计良好的排序实现检测到数据几乎已排序，则实际上可能会退回到这种插入排序，为输入提供 O(n) 排序，其中只有一个常量元素数在错误的位置，否则为 O(n log n)。特别是，java.util.Arrays.sort和 java.util.Collections.sort以这种方式实现。如果您的 Util.sort 也是这样实现的，那么您的算法已经是 O(n)。

在任何情况下，除非您每秒要记录数千个级别和数百万个游戏，否则 O(n) 和 O(n log n) 之间的差异不太可能对执行时间产生明显影响你的程序。