519. 随机翻转矩阵

尝试解答

我的思路是首先需建立map数组，记录matrix所有的row和col；
flip时随机值为0-数组长度为该数组的下标然后移除该项，这样每次随机都是有效的，最后返回；
直到数组为空。

class Solution {
    private matrix: number[][] = [];
    private mIndexList: number[] = [];
    private matrixChildMap!: Map<number, number[]>;

    constructor(private m: number, private n: number) {
        this.init();
    }

    flip(): number[] {
        if (!this.mIndexList.length) return [];
        const [m, mListIndex] = Solution.randItem(this.mIndexList);
        const childIndexList = this.matrixChildMap.get(m) as number[];
        const [n, nListIndex] = Solution.randItem(childIndexList);
        childIndexList.splice(nListIndex, 1)
        if (!childIndexList.length) {
            this.mIndexList.splice(mListIndex, 1)
        }
        this.matrix[m][n] = 1;
        return [m, n];
    }

    private static randItem<T>(arr: T[]): [T, number] {
        const index = ~~(Math.random() * arr.length);
        return [arr[index], index];
    }

    private init(){
        const matrix: number[][] = [];
        const child: number[] = []

        const nIndexList: number[] = []
        const matrixChildMap = new Map<number, number[]>();
        for (let i = 0; i < this.n; i++) {
            nIndexList.push(i);
            child.push(0);
        }

        const mIndexList: number[] = []
        for (let i = 0; i < this.m; i++) {
            matrix.push(child.slice())
            mIndexList.push(i);
            matrixChildMap.set(i, nIndexList.slice());
        }
        this.mIndexList = mIndexList;
        this.matrixChildMap = matrixChildMap;

        this.matrix = matrix;
    }

    reset(): void {
        this.init();
    }
}

结果卡在最后一步测试用例

再试

使用`${number},${number}`字符串作记录

class Solution {
    private matrix: number[][] = [];
    private indexList: `${number},${number}`[] = [];

    constructor(private m: number, private n: number) {
        this.init();
    }

    flip(): number[] {
        if (!this.indexList.length) return [];
        const index = ~~(Math.random() * this.indexList.length);
        const item = this.indexList.splice(index,1)[0];
        const [m,n] = item.split(",").map(Number);
        this.matrix[m][n] = 1;
        return [m, n];
    }
    
    private init(){
        const matrix: number[][] = [];
        const {m,n} = this;
        const indexList: `${number},${number}`[] = []
        for (let i = 0; i < m; i++) {
            const child: number[] = []
            for (let j = 0; j < n; j++) {
                child.push(0);
                indexList.push(`${i},${j}`)
            }
            matrix.push(child.slice())
        }
        this.indexList = indexList;

        this.matrix = matrix;
    }

    reset(): void {
        this.init();
    }
}

结果leetcode的ts版本太低了，不支持`${number},${number}`这种字符串模版类型。
再改

class Solution {
    private matrix: number[][] = [];
    private indexList: string[] = [];

    constructor(private m: number, private n: number) {
        this.init();
    }

    flip(): number[] {
        if (!this.indexList.length) return [];
        const index = ~~(Math.random() * this.indexList.length);
        const item = this.indexList.splice(index,1)[0];
        const [m,n] = item.split(",").map(Number);
        this.matrix[m][n] = 1;
        return [m, n];
    }

    private init(){
        const matrix: number[][] = [];
        const {m,n} = this;
        const indexList: string[] = []
        for (let i = 0; i < m; i++) {
            const child: number[] = []
            for (let j = 0; j < n; j++) {
                child.push(0);
                indexList.push(`${i},${j}`)
            }
            matrix.push(child.slice())
        }
        this.indexList = indexList;

        this.matrix = matrix;
    }

    reset(): void {
        this.init();
    }
}

还是不行，最后一个用例报另外一个错

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

第三次尝试

使用[number,number]元组的方式记录

class Solution {
    private matrix: number[][] = [];
    private indexList: [number, number][] = [];

    constructor(private m: number, private n: number) {
        this.init();
    }

    flip(): number[] {
        if (!this.indexList.length) return [];
        const index = ~~(Math.random() * this.indexList.length);
        const item = this.indexList.splice(index, 1)[0];
        const [m, n] = item;
        this.matrix[m][n] = 1;
        return item;
    }

    private init() {
        const matrix: number[][] = [];
        const {m, n} = this;
        const indexList: [number, number][] = []
        for (let i = 0; i < m; i++) {
            const child: number[] = []
            for (let j = 0; j < n; j++) {
                child.push(0);
                indexList.push([i, j])
            }
            matrix.push(child.slice())
        }
        this.indexList = indexList;

        this.matrix = matrix;
    }

    reset(): void {
        this.init();
    }
}

这比字符串的性能还差，到18题就不行了。
都不行，看来不是map方式的问题。
仔细想想其实matrix没有用，毕竟不是真的让你设置为1，所以得去掉matrix。

去掉matrix

class Solution {
    private indexList: string[] = [];

    constructor(private m: number, private n: number) {
        this.init();
    }

    flip(): number[] {
        if(!this.indexList.length) return [];
        const index = ~~(Math.random() * this.indexList.length);
        const item = this.indexList.splice(index,1)[0];
        return item.split(",").map(Number);
    }

    private init() {
        const {m, n} = this;
        const indexList: string[] = []
        for (let i = 0; i < m; i++) {
            for (let j = 0; j < n; j++) {
                indexList.push(`${i},${j}`)
            }
        }
        this.indexList = indexList;
    }

    reset(): void {
        this.init();
    }
}

拿去测试，结果还是内存占用太大，卡在最后。

最后

我的答案首先需建立map数组，然后flip时只要随机移除对应的，最终为空。除非去掉建立map数组，才能节省掉这份占用最大的空间。绞尽脑汁，还是没想出优化方法，最后去看了官方答案

class Solution {
    private total: number;
    private map: Map<number,number> = new Map();

    constructor(private m: number, private n: number) {
        this.total = m * n;
    }

    flip(): number[] {
        const x = ~~(Math.random() * this.total);
        this.total--;
        // 查找位置 x 对应的映射
        const idx = this.map.get(x) || x;
        // 将位置 x 对应的映射设置为位置 total 对应的映射
        this.map.set(x, this.map.get(this.total) || this.total);
        return [~~(idx / this.n), idx % this.n];
    }


    reset(): void {
        this.total = this.m * this.n;
        this.map.clear();
    }
}

其实如果没有空间要求的话，上面的也能解答，但是数据量大就不行了，空间占太多了。
这题的答案有点绕，有点难以理解，但是用途挺大的，可以使用到代码优化上面去，值得花时间去理解。