forked from liuyubobobo/Play-Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
main3.cpp
88 lines (68 loc) · 1.97 KB
/
main3.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
/// 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;
}