【LeetCode笔记 - 每日一题】519. 随机翻转矩阵（Java、随机、双指针）

题目描述

• 又是涉及到均等概率的随机～
  

思路 && 代码

• 用的题解区三叶的代码～写得是真的好！不论题目，但抄一遍代码都能觉得有收获！
• 维度转化：并没有创造二维数组（太大了）。而是转化成一维的场景。
• 双指针：每次随机一个[0, m * n)的值，然后向左、向右查找第一个没访问过的值

class Solution {
    int m;
    int n;
    Random random = new Random();
    Set<Integer> set = new HashSet<>(); // 记录访问

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
    }
    
    public int[] flip() {
        int toLeft = random.nextInt(m * n), toRight = toLeft; // 双指针，双向延伸
        while(toLeft >= 0 && set.contains(toLeft)) toLeft--;
        while(toRight < m * n && set.contains(toRight)) toRight++;
        int index = toLeft >= 0 && !set.contains(toLeft) ? toLeft : toRight; // 二选一
        set.add(index);
        return new int[]{index / n, index % n}; // 一维 =》二维
    }
    
    public void reset() {
        set.clear();
    }
}

• 自己写一遍：

class Solution {
    int m, n;
    Set<Integer> set = new HashSet<>();
    Random random = new Random();

    public Solution(int m, int n) {
        this.m = m;
        this.n = n;
    }
    
    public int[] flip() {
        int toLeft = random.nextInt(m * n), toRight = toLeft;
        while(toLeft >= 0 && set.contains(toLeft)) toLeft--;
        while(toRight < m * n && set.contains(toRight)) toRight++;
        int index = toLeft >= 0 && !set.contains(toLeft) ? toLeft : toRight;
        set.add(index);
        return new int[]{index / n, index % n};
    }
    
    public void reset() {
        set.clear();
    }
}