資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告