資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中的帶黑名單的隨機選取
假設我們有一個名為 B 的黑名單。這正在區間 [0, N) 內保留唯一整數，我們必須定義一個函式，以從 NOT in B 的範圍 [0, N) 中返回一個均勻的隨機整數。我們將透過減少 random() 嘗試使這個函式更最佳化。函式呼叫。假設輸入陣列如下
為了解決這個問題，我們將遵循以下步驟 -
定義一個 map
- 我們將使用 N 和陣列 v 初始化。
- 對於 initalize i := 0，當 i < v 的 size 時，更新（將 i 增加 1），執行 -
- 如果 v[i] < N，則：，m[v[i]] := -1
- M := N – m 的 size
- n := v 的 size
- 對於 initalize i := 0，當 i < v 的 size 時，更新（將 i 增加 1），執行 -
- 如果 v[i] < M，則 -
- 將 N 減少 1
- 當 N 在 m 中時，執行 -
- 將 N 減少 1
- m[v[i]] := N
- 如果 v[i] < M，則 -
- 定義一個函式 pick()
- x := 隨機數模 M
- 返回（如果 x 存在於 m 中，則為 m[x]，否則為 x）
讓我們看看以下實現以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int M;
map <int,int> m;
Solution(int N, vector<int>& v) {
for(int i = 0; i < v.size(); i++){
if(v[i] < N) m[v[i]] = -1;
}
M = N - (int)(m.size());
int n = v.size();
for(int i = 0; i < v.size(); i++){
if(v[i] < M){
while(m.count(--N));
m[v[i]] = N;
}
}
}
int pick() {
int x = rand() % M;
return m.count(x)? m[x] : x;
}
};
main(){
vector<int> v = {2};
Solution ob(4,v);
cout << (ob.pick()) << endl;
cout << (ob.pick()) << endl;
cout << (ob.pick()) << endl;
}輸入
Give N = 4 and array [2]
輸出
1 1 0
更新於： 2020-06-02
180 次瀏覽
廣告