数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++随机翻转矩阵
假设我们有一个n_rows行n_cols列的二进制矩阵。所有值最初都为0。我们需要定义一个函数flip()，该函数随机选择一个值为0的元素，将其更改为1，然后返回该值的坐标[row.id, col.id]。此外，我们还需要编写另一个函数reset()，将所有值重置为0。我们需要尽量减少对系统Math.random()的调用次数，并优化时间和空间复杂度。
如果我们有一个2x3的矩阵，并且我们调用flip四次，那么结果将是[0,1]，[1,2]，[1,0]，[1,1]。
为了解决这个问题，我们将遵循以下步骤：
- 创建一个名为holes的映射。
- 在初始化器中，执行以下操作：
- 初始化随机数生成器，n := 行数，m := 列数，
- size := n * m
- 在flip方法中，执行以下操作：
- id := 随机数 mod size，size减1，rid := id
- 如果holes中存在id，则id := holes[id]
- holes[rid] := size在holes中时为holes[size]，否则为size
- 返回一个坐标对(id / m, id mod m)
- 在reset方法中，执行以下操作：
- size := n x m，并清空holes
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
unordered_map <int, int> holes;
int n;
int m;
int size;
Solution(int n_rows, int n_cols) {
srand(time(NULL));
n = n_rows;
m = n_cols;
size = n * m;
}
vector<int> flip() {
int id = rand() % size;
size--;
int rid = id;
if(holes.count(id)){
id = holes[id];
}
holes[rid] = holes.count(size) ? holes[size] : size;
return {id / m, id % m};
}
void reset() {
size = n * m;
holes.clear();
}
};
main(){
Solution ob(2,2);
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
print_vector(ob.flip());
}输入
Initialize the constructor using 2,2 and call flip four times
输出
[1, 1, ] [0, 0, ] [1, 0, ] [0, 1, ]
更新于：2020年5月2日
235 次浏览
广告