Random Flip Matrix Solutions in C++

/// Source : https://leetcode.com/problems/random-flip-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;


/// Rejection Sampling
///
/// Time Complexty: O(m*n)
/// Space Complexity: O(min(len(call of flip), m*n))
class Solution {

private:
    int m, n;
    unordered_set<int> ones;

public:
    Solution(int n_rows, int n_cols): m(n_rows), n(n_cols) {
        ones.clear();
    }

    vector<int> flip() {

        int randNum;
        do{
            randNum = rand() % (m * n);
        }while(ones.find(randNum) != ones.end());
        ones.insert(randNum);
        return {randNum / n, randNum % n};
    }

    void reset() {
        ones.clear();
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/random-flip-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;


/// Using Buckets to find the kth unflipped position
///
/// Time Complexty: O(sqrt(m*n))
/// Space Complexity: O(min(len(call of flip), m*n))
class Solution {

private:
    int m, n;
    int bucket_sz;
    vector<unordered_set<int>> buckets;
    int left;

public:
    Solution(int n_rows, int n_cols): m(n_rows), n(n_cols) {

        bucket_sz = sqrt(m * n);
        reset();
    }

    vector<int> flip() {

        int randNum = rand() % left;
        left --;

        int index = 0, ret = -1;
        for(int i = 0; i < buckets.size(); i ++){
            int left_in_bucket = min(bucket_sz, m * n - i * bucket_sz) - buckets[i].size();
            if(randNum >= index && randNum < index + left_in_bucket){
                int k = randNum - index;
                for(int j = i * bucket_sz; j < min((i + 1) * bucket_sz, m * n); j ++)
                    if(buckets[i].find(j) == buckets[i].end()){
                        if(!k){
                            ret = j;
                            buckets[i].insert(j);
                            break;
                        }
                        k --;
                    }
                if(ret != -1)
                    break;
            }
            else
                index += left_in_bucket;
        }
        assert(ret != -1);
        return {ret / n, ret % n};
    }

    void reset() {

        buckets.clear();
        for(int i = 0; i < m * n; i += bucket_sz)
            buckets.push_back(unordered_set<int>());
        left = m * n;
    }

    static void print_vec(const vector<int>& vec){
        for(int e: vec)
            cout << e << " ";
        cout << endl;
    }
};


int main() {

    Solution solution(2, 2);
    for(int i = 0; i < 4; i ++)
        Solution::print_vec(solution.flip());

    return 0;
}

/// Source : https://leetcode.com/problems/random-flip-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <algorithm>
#include <cassert>

using namespace std;


/// Using Buckets to find the kth unflipped position
/// Using binary search:)
/// \
/// Time Complexty: O(sqrt(m*n))
/// Space Complexity: O(min(len(call of flip), m*n))
class Solution {

private:
    int m, n;
    int bucket_sz;
    vector<unordered_set<int>> buckets;
    vector<int> start;

public:
    Solution(int n_rows, int n_cols): m(n_rows), n(n_cols) {

        bucket_sz = sqrt(m * n);
        reset();
    }

    vector<int> flip() {

//        Solution::print_vec(start);

        int randNum = rand() % start.back();
        int index = upper_bound(start.begin(), start.end(), randNum) - start.begin();
        index --;
//        cout << "find " << randNum << " in " << index << " bucket." << endl;

        int k = randNum - start[index];
        int ret = -1;
        for(int i = index * bucket_sz; ; i ++)
            if(buckets[index].find(i) == buckets[index].end()){
                if(!k){
                    ret = i;
                    buckets[index].insert(i);
                    break;
                }
                k --;
            }

        for(int i = index + 1; i < start.size(); i ++)
            start[i] --;
        return {ret / n, ret % n};
    }

    void reset() {

        buckets.clear();
        start.clear();

        start.push_back(0);
        for(int i = 0; i < m * n; i += bucket_sz){
            buckets.push_back(unordered_set<int>());
            start.push_back(min(start.back() + bucket_sz, m * n));
        }
    }

    static void print_vec(const vector<int>& vec){
        for(int e: vec)
            cout << e << " ";
        cout << endl;
    }
};


int main() {

    Solution solution(2, 2);
    for(int i = 0; i < 4; i ++)
        Solution::print_vec(solution.flip());

    return 0;
}

/// Source : https://leetcode.com/problems/random-flip-matrix/description/
/// Author : liuyubobobo
/// Time   : 2018-08-28

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>

using namespace std;


/// Position redirection
/// Time Complexty: O(1)
/// Space Complexity: O(min(len(call of flip), m*n))
class Solution {

private:
    int m, n;
    int left;
    unordered_map<int, int> redirection;

public:
    Solution(int n_rows, int n_cols): m(n_rows), n(n_cols) {
        reset();
    }

    vector<int> flip() {

        int randNum = rand() % left;
        left --;

        int ret = randNum;
        if(redirection.find(randNum) != redirection.end())
            ret = redirection[randNum];

        if(redirection.find(left) == redirection.end())
            redirection[randNum] = left;
        else
            redirection[randNum] = redirection[left];

        return {ret / n, ret % n};
    }

    void reset() {
        left = m * n;
        redirection.clear();
    }
};


void print_vec(const vector<int>& vec){
    for(int e: vec)
        cout << e << " ";
    cout << endl;
}

int main() {

    Solution solution(2, 2);
    for(int i = 0; i < 4; i ++)
        print_vec(solution.flip());

    return 0;
}