leetcode519. Random Flip Matrix

제목 요구
You are given the number of rows n_rows and number of columns n_cols of a 2D binary matrix where all values are initially 0. Write a function flip which chooses a 0 value uniformly at random, changes it to 1, and then returns the position [row.id, col.id] of that value. Also, write a function reset which sets all values back to 0. Try to minimize the number of calls to system's Math.random() and optimize the time and space complexity.
Note:

1 <= n_rows, n_cols <= 10000

0 <= row.id < n_rows and 0 <= col.id < n_cols

flip will not be called when the matrix has no 0 values left.

the total number of calls to flip and reset will not exceed 1000.

Example 1:

Input: 
["Solution","flip","flip","flip","flip"]
[[2,3],[],[],[],[]]
Output: [null,[0,1],[1,2],[1,0],[1,1]]

Example 2:

Input: 
["Solution","flip","flip","reset","flip"]
[[1,2],[],[],[],[]]
Output: [null,[0,0],[0,1],null,[0,0]]
Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, n_rows and n_cols. flip and reset have no arguments. Arguments are always wrapped with a list, even if there aren't any.
지금 n 이 있다 고 가정 해 봐.rows 행 과 ncolumns 열의 행렬, 이 행렬 의 초기 요소 값 은 0 입 니 다.flip 방법 을 호출 할 때 행렬 의 값 이 0 인 칸 을 무 작위 로 선택 하고 1 로 설정 하여 칸 의 행렬 좌 표를 되 돌려 야 합 니 다.reset 방법 은 행렬 을 초기 상태 로 재 구성 합 니 다.가능 한 한 random 방법의 호출 횟수 를 줄 여야 합 니 다.
아이디어 와 코드
사실 가장 직관 적 인 방법 은 무 작위 수 를 사용 하여 무 작위 줄 과 열 을 각각 생 성 한 다음 에 이 위치의 값 이 0 인지 아 닌 지 를 판단 하 는 것 이다.0 이 아니라면 0 인 칸 을 찾 을 때 까지 무 작위 행렬 을 만 들 고 판단 을 계속 합 니 다.
여기 서 첫 번 째 최 적 화 는 바로 2 차원 배열 을 1 차원 화 하 는 것 이다. 즉, i 행 k 열 이라는 좌 표 는 i*n_columns+k 을 통 해 유일한 정수 표현 형식 을 얻 을 수 있다.우 리 는 n_rows*n_colums 범위 내 에서 무 작위 정 수 를 생 성하 고 2 차원 좌표 로 전환 하면 무 작위 방법의 집행 횟수 를 절반 으로 줄 일 수 있다.
그러면 그 다음 의 최적화 사 고 는 우리 가 아직 옮 겨 다 니 지 않 은 다음 표 집합 을 저장 할 수 있다 는 것 을 직관 적 으로 생각 할 수 있다.매번 집합 크기 를 난수 로 생 성 하 는 경 계 를 집합 에서 제거 하면 이번 에는 이 위치의 칸 을 뒤 집 는 것 을 의미한다.
그러나 이러한 구 조 를 List 로 직접 저장 하 는 것 은 심각 한 성능 문제 가 있 을 수 있다.하나의 1000*1000 행렬 이 라 고 가정 하면 초기 List 에 1000000 개의 선택 되 지 않 은 칸 을 저장 해 야 하 며 시간 과 공간 에 있어 서 는 받 아들 일 수 없습니다.그렇다면 뒤 집 히 지 않 은 요 소 를 다른 형식 으로 기록 할 수 있 는 방법 은 없 을 까?
앞에서 말 했 듯 이 2 차원 배열 의 하 표 는 1 차원 배열 의 하 표 로 바 뀔 수 있다.우 리 는 이러한 장면 을 상상 할 수 있다. 이 1 차원 배열 에 대해 아래 표 가 펼 쳐 질 때마다 이 아래 표 와 현재 펼 쳐 지지 않 은 마지막 요소 위 치 를 교환 할 수 있다.우 리 는 앞의 마지막 요 소 를 부 르 는 새로운 위 치 를 기록 하면 된다.예 를 들 어 2*3 의 행렬 은 길이 가 6 인 1 차원 행렬 로 펼 칠 수 있 고 그 요 소 는 각각 0,1,2,3,4,5 이다.
첫 번 째 flip 는 랜 덤 으로 아래 표 시 를 생 성 합 니 다. 2 와 5 를 교환 하고 2 라 는 위치 에 있 는 새로운 요소 5 (2: 5) 를 기록 합 니 다. 두 번 째 flip 는 랜 덤 으로 아래 표 시 를 생 성 합 니 다. 1 과 4 를 부 르 고 1 이 위치 에 있 는 새로운 요 소 는 4 (2: 5, 1: 4) 세 번 째 flip 는 랜 덤 으로 아래 표 시 를 생 성 합 니 다. 이때 우 리 는 2 에 저 장 된 요소 가 5 라 는 것 을 발 견 했 기 때문에 5 로 돌아 갑 니 다. 기록 2 에 있 는 새로운 요 소 는 3 입 니 다.(2:3, 1:4)...
이렇게 되면 무 작위 로 생 성 된 아래 표 시 는 기록 에 없 을 때 아래 표 시 된 위 치 는 그 자체 입 니 다. 그렇지 않 으 면 교 환 된 위치 입 니 다. 매번 아래 표 시 된 요 소 를 마지막 으로 펼 쳐 지지 않 은 아래 표 시 를 업데이트 해 야 합 니 다.

    Map map;
    Random                r;
    int rowCount;
    int columnCount;
    int flipCount;
    public Solution(int n_rows, int n_cols) {
        map = new HashMap<>();
        r = new Random();
        rowCount = n_rows;
        columnCount = n_cols;
        flipCount = rowCount * columnCount;
    }

    public int[] flip() {
        int randomIndex = r.nextInt(flipCount--);
        int value = map.getOrDefault(randomIndex, randomIndex);
        map.put(randomIndex, map.getOrDefault(flipCount, flipCount));
        return new int[]{value/columnCount, value%columnCount};
    }

    public void reset() {
        map.clear();
        flipCount = rowCount * columnCount;
    }