Posts tagged as “random”

花花酱 LeetCode 883. Generate Random Point in a Circle

By zxi on July 28, 2018

Problem

Given the radius and x-y positions of the center of a circle, write a function randPoint which generates a uniform random point in the circle.

Note:

input and output values are in floating-point.
radius and x-y position of the center of the circle is passed into the class constructor.
a point on the circumference of the circle is considered to be in the circle.
randPoint returns a size 2 array containing x-position and y-position of the random point, in that order.

Example 1:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[1,0,0],[],[],[]]
Output: [null,[-0.72939,-0.65505],[-0.78502,-0.28626],[-0.83119,-0.19803]]

Example 2:

Input: 
["Solution","randPoint","randPoint","randPoint"]
[[10,5,-7.5],[],[],[]]
Output: [null,[11.52438,-8.33273],[2.46992,-16.21705],[11.13430,-12.42337]]

Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution‘s constructor has three arguments, the radius, x-position of the center, and y-position of the center of the circle. randPoint has no arguments. Arguments are always wrapped with a list, even if there aren’t any.

Solution: Polar Coordinate

uniform sample an angle a: [0, 2*Pi)

uniform sample a radius r: [0, 1)

Number of random points in a cycle should be proportional to the square of distance to the center.

e.g. there are 4 times of points with distance d than points with distance d/2.

Thus sqrt(r) is uniformly distributed.

r’ = sqrt(r),

C++

// Author: Huahua

// Running time: 116 ms

class Solution {

public:

Solution(double radius, double x_center, double y_center)

:r_(radius), x_(x_center), y_(y_center) {}

vector<double> randPoint() {

double a = rand() / static_cast<double>(RAND_MAX) * 2 * M_PI;

double r = sqrt(rand() / static_cast<double>(RAND_MAX)) * r_;

return {x_ + r * cos(a), y_ + r * sin(a)};

}

private:

double r_;

double x_;

double y_;

};

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

By zxi on July 16, 2018

Problem

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

Example 1:

Input: 1
Output: [7]

Example 2:

Input: 2
Output: [8,4]

Example 3:

Input: 3
Output: [8,1,10]

Note:

rand7 is predefined.
Each testcase has one argument: n, the number of times that rand10 is called.

Solution: Math

Time complexity: O(49/40) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int target = 40;

while (target >= 40)

target = 7 * (rand7() - 1) + (rand7() - 1);

return target % 10 + 1;

}

};

Time complexity: O(7/6 + 7 / 5) = O(1)

// Author: Huahua

// Running time: 112 ms

class Solution {

public:

int rand10() {

int i = INT_MAX;

int j = INT_MAX;

while (i > 6) i = rand7(); // i = [1, 2, 3, 4, 5, 6]

while (j > 5) j = rand7(); // j = [1, 2, 3, 4, 5]

return j + 5 * (i & 1);

}

};

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed

By zxi on September 17, 2017

https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/description/

Problem:

Design a data structure that supports all following operations in average O(1) time.

Note: Duplicate elements are allowed.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.

Idea:

Hashtable + array

Solution:

// Author: Huahua

// Running time: 49 ms

class RandomizedCollection {

public:

/** Initialize your data structure here. */

RandomizedCollection() {}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

bool insert(int val) {

m_[val].push_back(vals_.size());

vals_.emplace_back(val, m_[val].size() - 1);

return m_[val].size() == 1u;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

bool remove(int val) {

if (!m_.count(val)) return false;

int index_to_evict = m_[val].back();

const auto& last_entry = vals_.back();

// Update index

m_[last_entry.first][last_entry.second] = index_to_evict;

// Swap vals

swap(vals_.back(), vals_[index_to_evict]);

// Clenup

vals_.pop_back();

m_[val].pop_back();

if (m_[val].empty()) m_.erase(val);

return true;

}

/** Get a random element from the collection. */

int getRandom() {

return vals_[rand() % vals_.size()].first;

}

private:

// val -> indices array: indices in vals_

unordered_map<int, vector<int>> m_;

// {val, index in the indices array}

vector<pair<int,int>> vals_;

};

Java

// Author: Huahua

// Running time: 122 ms (<94.53%)

class RandomizedCollection {

class Entry {

public int value;

public int index;

public Entry(int val, int idx) {

value = val;

index = idx;

}

private Map<Integer, List<Integer>> m;

private List<Entry> vals;

private Random rand;

/** Initialize your data structure here. */

public RandomizedCollection() {

m = new HashMap<>();

vals = new ArrayList<>();

rand = new Random();

}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */

public boolean insert(int val) {

List<Integer> l = m.getOrDefault(val, new ArrayList<Integer>());

l.add(vals.size());

m.put(val, l);

vals.add(new Entry(val, l.size() - 1));

return l.size() == 1;

}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */

public boolean remove(int val) {

if (!m.containsKey(val)) return false;

List<Integer> l = m.get(val);

int index_to_evict = l.get(l.size() - 1);

Entry last_entry = vals.get(vals.size() - 1);

// Update index

m.get(last_entry.value).set(last_entry.index, index_to_evict);

// Swap vals

vals.set(index_to_evict, last_entry);

// Cleanup

vals.remove(vals.size() - 1);

l.remove(l.size() - 1);

if (l.size() == 0) m.remove(val);

return true;

}

/** Get a random element from the collection. */

public int getRandom() {

return vals.get(rand.nextInt(vals.size())).value;

}

Related Problems:

花花酱 LeetCode 380. Insert Delete GetRandom O(1)

By zxi on September 16, 2017

Problem:

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Idea:

Hashtable + array

Time complexity:

O(1)

Solution:

// Author: Huahua

// Running time: 49 ms

class RandomizedSet {

public:

/** Initialize your data structure here. */

RandomizedSet() {}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

bool insert(int val) {

if(m_.count(val)) return false;

m_[val] = vals_.size();

vals_.push_back(val);

return true;

}

/** Removes a value from the set. Returns true if the set contained the specified element. */

bool remove(int val) {

if(!m_.count(val)) return false;

int index = m_[val];

m_[vals_.back()] = index;

m_.erase(val);

std::swap(vals_[index], vals_.back());

vals_.pop_back();

return true;

}

/** Get a random element from the set. */

int getRandom() {

int index = rand() % vals_.size();

return vals_[index];

}

private:

// val -> index in the array

unordered_map<int, int> m_;

vector<int> vals_;

};

Related Problems:

Posts tagged as “random”

花花酱 LeetCode 883. Generate Random Point in a Circle

Problem

Solution: Polar Coordinate

C++

花花酱 LeetCode 872. Implement Rand10() Using Rand7()

Problem

Solution: Math

花花酱 LeetCode 382. Linked List Random Node

Problem:

Solution:

花花酱 LeetCode 381. Insert Delete GetRandom O(1) – Duplicates allowed

花花酱 LeetCode 380. Insert Delete GetRandom O(1)