Random Flip false to true - Google Interview

1. 给一个2D matrix，bool 型，初始状态是都是false,要求写一个flip函数，实现把其中一个element由false变成true。 要求是所有false element被翻转的概率相等。
-- flip will be called repeatedly
1. 应该是random with blacklist，2维转1维,（i,j)->(i*n+j). from: 1point3acres.com/bbs
不知道有没有更好地办法，因为当blacklist也就是选过的值增多的时候，复杂度可以到O(mn)，
搞一个 unordered_set<pair<int,int>> coordinates 来存所有false element的坐标。然后产生一个[0,coordinates.size()-1]的随机数x，coordinates[x]就是我们要翻转的element啦。 存coordinates 要O(n) time and O(n) space. 随机数和翻转都是O(1),所以总的复杂度是O(n).
void flip(vector<vector<bool>> & matrix) {
        int row = matrix.size();
        if (row == 0) return;
        int col = matrix.size();
        if (col == 0) return;
        vector<pair<int,int>> co;  // stores all the false elements’ coordinates
        for (int i=0;i<row;i++) {
                for (int j=0;j<col;j++) {
                        if (matrix[j] == false) co.push_back(make_pair<i,j>);
}
}
        myFlip(matrix,co);
}

void myFlip(vector<vector<bool>> & matrix, vector<pair<int,int>> & co) {
        int total = co.size();
        int ran = rand()%total;  // generate a number between 0 and total-1
        inr r = co[ran].first;
        int c = co[ran].second;
        matrix[r][c] = true;
        co.erase(co.begin() + ran);  // erase (r ,c)
        return;
}

我说一个flip()是O(M+N)时间的实现，空间复杂度是O(M)。其中M，N分别是矩阵的行列数。

一开始先创建一个长为M的cum数组。cum[i]代表“到第i行（含第i行）为止，矩阵中有多少个false”。比如大矩阵是：
0 1 0 0
1 0 0 1
0 0 1 0
那么cum数组就是
[3 5 9]

我们用cum数组来决定下一个随机数出现在哪一行。比如对[3 5 9]，我们先产生一个1~9之间的随机数，比如4，然后在cum中找“第一个大于等于4”的数字，是第二个数5。那么我们就在第二行产生随机数。然后，因为5和其前面的数3的差为2，说明这一行有2个false，那么我们再产生一个[1 2]间的随机数，比如1。 然后遍历第5行，直到找到第1个0为止。这一步花费O(N)时间.

然后我们要更新cum数组，具体做法是把第二个数字和之后的数字都减1，最后cum变成[3 4 8]。这一步花费O(M)时间。

其实你生成一次随机数就可以了，比如你的例子中的4，那么4-3就是它在第二行中的位置。

When can't use extra space, 用reservior resampling

private static void flip(boolean[][] table){
int count = 1;
int m = table.length;
int n = table[0].length;

int[] index = new int[]{-1, -1};
Random r = new Random();

for(int i = 0; i < m; i++){
    for(int j = 0; j < n; j++){
        if(table[i][j] == false){
            int x = r.nextInt(count);
            if(x == 0){
                index[0] = i;
                index[1] = j;
            }
          
            count++;
        }
    }
}

if(index[0] != -1){
    table[index[0]][index[1]] = true;
}
}
所以最后总时间是O(M+N)，空间是cum数组消耗的O(M)。