原题链接

LeetCode

class RandomizedSet {
    elements: number[];
    hash: Map<number, number>
    constructor() {
        this.elements = [];
        this.hash = new Map();
    }

    insert(val: number): boolean {
        if(this.hash.has(val)) {
            return false;
        }

        const index = this.elements.push(val);
        this.hash.set(val, index - 1);
        return true;
    }

    remove(val: number): boolean {
        if(!this.hash.has(val)) {
            return false;
        }
        const index = this.hash.get(val)!;
        const lastEle = this.elements[this.elements.length - 1];
        // 不能直接删 否则导致全体元素的位置都错位了
        // this.elements.splice(index, 1);
        this.elements[index] = lastEle;
        this.hash.set(lastEle, index);
        this.elements.pop();
        this.hash.delete(val);
        return true;
    }

    getRandom(): number {
        const random = Math.floor(Math.random() * this.elements.length);
        return this.elements[random];
    }
}