https://leetcode.com/problems/shuffle-an-array/description/
class Solution {
vector<int> nums;
public:
Solution(vector<int> nums) {
this->nums = nums;
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return nums;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
int N = nums.size();
vector<int> res(nums);
for(int i=0; i<N; i++) {
int j = rand() % (N-i);
swap(res[i], res[i+j]);
}
return res;
}
};
Showing posts with label Random. Show all posts
Showing posts with label Random. Show all posts
Thursday, October 12, 2017
382. Linked List Random Node
https://leetcode.com/problems/linked-list-random-node/description/
Solution 1. Reservoir sampling
class Solution {
ListNode* head;
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
this->head = head;
}
/** Returns a random node's value. */
int getRandom() {
ListNode* node = head;
int res = node->val;
node = node->next;
int k=1, kpi=2;
while(node) {
if(rand()%kpi == 0) res = node->val;
kpi++;
node = node->next;
}
return res;
}
};
Solution 2.
class Solution {
int N;
int len = 1000;
ListNode* hd;
vector<ListNode*> vl;
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
hd = head;
ListNode* p=head;
N = 0;
while(p) {
if(N%len == 0) vl.push_back(p);
N++;
p = p->next;
}
}
/** Returns a random node's value. */
int getRandom() {
random_device rd;
uniform_int_distribution<int> dist(0, N-1);
int n = dist(rd);
ListNode*p = vl[n/len];
n = n%len;
while(n) {
p = p->next;
n--;
}
return p->val;
}
};
Solution 1. Reservoir sampling
class Solution {
ListNode* head;
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
this->head = head;
}
/** Returns a random node's value. */
int getRandom() {
ListNode* node = head;
int res = node->val;
node = node->next;
int k=1, kpi=2;
while(node) {
if(rand()%kpi == 0) res = node->val;
kpi++;
node = node->next;
}
return res;
}
};
Solution 2.
class Solution {
int N;
int len = 1000;
ListNode* hd;
vector<ListNode*> vl;
public:
/** @param head The linked list's head.
Note that the head is guaranteed to be not null, so it contains at least one node. */
Solution(ListNode* head) {
hd = head;
ListNode* p=head;
N = 0;
while(p) {
if(N%len == 0) vl.push_back(p);
N++;
p = p->next;
}
}
/** Returns a random node's value. */
int getRandom() {
random_device rd;
uniform_int_distribution<int> dist(0, N-1);
int n = dist(rd);
ListNode*p = vl[n/len];
n = n%len;
while(n) {
p = p->next;
n--;
}
return p->val;
}
};
Wednesday, October 11, 2017
Random
http://en.cppreference.com/w/cpp/numeric/random/rand
#include <cstdlib> #include <iostream> #include <ctime> int main() { std::srand(std::time(0)); // use current time as seed for random generator int random_variable = std::rand(); std::cout << "Random value on [0 " << RAND_MAX << "]: " << random_variable << '\n'; }
#include <random>
std::random_device rd;
std::uniform_int_distribution<int> dist(0, 9);
for (int n = 0; n < 10; ++n) {
std::cout<<dist(rd)<<"\n";
http://en.cppreference.com/w/cpp/header/random
http://en.cppreference.com/w/cpp/numeric/random/random_device
http://en.cppreference.com/w/cpp/numeric/random/uniform_int_distribution
Subscribe to:
Posts (Atom)