编辑代码

class SkipListNode {
    id: number;
    score: number;
    power: number;
    timestamp: number;
    next: SkipListNode[];
    span: number[];

    constructor(id: number, score: number, power: number, timestamp: number, level: number) {
        this.id = id;
        this.score = score;
        this.power = power;
        this.timestamp = timestamp;
        this.next = new Array(level).fill(null);
        this.span = new Array(level).fill(0);
    }
}

class SkipList {
    private head: SkipListNode;
    private maxLevel: number;
    private level: number;
    private p: number; // 概率因子

    constructor(maxLevel: number, p: number) {
        this.maxLevel = maxLevel;
        this.level = 1;
        this.p = p;
        this.head = new SkipListNode(-1, Number.MAX_SAFE_INTEGER, 0, 0, maxLevel);
    }

    private randomLevel(): number {
        let lvl = 1;
        while (Math.random() < this.p && lvl < this.maxLevel) {
            lvl++;
        }
        return lvl;
    }

    private compareNodes(node1: SkipListNode, node2: SkipListNode): number {
        if (node1.score !== node2.score) {
            return node2.score - node1.score; // 高分在前
        }
        if (node1.power !== node2.power) {
            return node2.power - node1.power; // 高power在前
        }
        return node1.timestamp - node2.timestamp; // 早加入的在前
    }

    insert(id: number, score: number, power: number, timestamp: number): void {
        const update = new Array(this.maxLevel).fill(this.head);
        const ranks = new Array(this.maxLevel).fill(0);
        let current = this.head;

        for (let i = this.level - 1; i >= 0; i--) {
            while (current.next[i] !== null && this.compareNodes(current.next[i], new SkipListNode(id, score, power, timestamp, 0)) > 0) {
                ranks[i] += current.span[i];
                current = current.next[i];
            }
            update[i] = current;
        }

        const newLevel = this.randomLevel();
        if (newLevel > this.level) {
            for (let i = this.level; i < newLevel; i++) {
                update[i] = this.head;
                ranks[i] = 0;
                this.head.span[i] = this.level;
            }
            this.level = newLevel;
        }

        const newNode = new SkipListNode(id, score, power, timestamp, newLevel);
        for (let i = 0; i < newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            newNode.span[i] = update[i].span[i] - (ranks[i] - ranks[newLevel]);
            update[i].span[i] = ranks[i] - ranks[newLevel] + 1;
            update[i].next[i] = newNode;
        }

        for (let i = newLevel; i < this.level; i++) {
            update[i].span[i]++;
        }
    }

findRankById(id: number): number {
    let rank = 0;
    let current = this.head;

    for (let i = this.level - 1; i >= 0; i--) {
        while (current.next[i] !== null && this.compareNodes(current.next[i], new SkipListNode(id, 0, 0, 0, 0)) > 0) {
            rank += current.span[i];
            current = current.next[i];
        }
        if (current.next[i] !== null && current.next[i].id === id) {
            return rank + current.span[i]; // 注意这里加current.span[i]，因为rank是从0开始的，并且需要加上当前节点的跨度
        }
    }
    return -1; // 如果没有找到该玩家
}

    getTop100Players(): SkipListNode[] {
        const top100: SkipListNode[] = [];
        let current = this.head.next[this.level - 1];

        for (let i = 0; i < 100 && current !== null; i++) {
            top100.push(current);
            current = current.next[this.level - 1];
        }

        return top100;
    }


}
       const skipList:SkipList = new SkipList(16, 0.5);

        // 插入一些玩家
        skipList.insert(1, 1000, 10, Date.now());
        skipList.insert(2, 1010, 20, Date.now());
        skipList.insert(3, 1000, 30, Date.now());
        skipList.insert(4, 1020, 40, Date.now());
        skipList.insert(5, 1030, 50, Date.now());

        // 查找玩家排名
        console.log("Rank of player with ID 3:", skipList.findRankById(3));

        // 获取前100名玩家
        const top100 = skipList.getTop100Players();
        console.log("Top 100 players:");
        top100.forEach(player => console.log(`ID: ${player.id}, Score: ${player.score}, Power: ${player.power}, Timestamp: ${player.timestamp}`));