Stuck at storyboarding of animated film n not know how to fix the issue.

**Next:** just draw. Draw anything you like. Then you’ll come up with the idea

Stuck at storyboarding of animated film n not know how to fix the issue.

**Next:** just draw. Draw anything you like. Then you’ll come up with the idea

Advertisements

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.

**Discussion:**

In C++, containers supporting insert with O(1) are *vector*, *list*, *unordered_map*, and *unordered_set*.

Containers remove by value with O(1) are *unordered_map*, *unordered_set*.

Container supporting random access is *vector*.

So, we can use *vector* AND *unordered_set* or *unordered_map* for the three functions. Then *unordered_set* or *unordered_map*? We have to use *vector* to store the values for the sake of random access with O(1). And a hash container (*unordered_set*, or *unordered_map*) to remove with O(1). But we need to figure out how to remove the values from the vector with O(1). Here we can build a connection between the hash container with the vector, so *unordered_map* wins: reference the same value in the *vector* by the value’s position.

insert and random access can easily being done with O(1) for *vector* and *unordered_map*. But for remove, it affects the *unordered_map*‘s reference in the vector. The instinct is removing the value from the *vector* by getting its position from *unordered_map*. But this will decrease the positions of all descending elements in the *vector*, which affects the references of the *unordered_map*. The time complexity could be up to linear O(n) if we do position update in the *unordered_map*, in worst case. So the instinct is O(n) on average for remove. After struggling.. I ended up finding a clever trick to remove with O(1) online: swapping the element to be removed with the last element in the *vector*, and updating the last element’s value in the *unordered_map* with the new position. exactly O(1) on average.

This is a LeetCode problem:

https://oj.leetcode.com/problems/median-of-two-sorted-arrays/

It is not hard to come out a solution with O(m + n) or O(log(m + n)), but it’s really tricky to deal with boundary conditions.

A O(log(m + n)) solution should use something like binary search. I referenced an answer in the discussion board, and wrote my O(log(m + n)) solution. The idea is to make the median index as the k of the k-lowest search problem. For even length, the two median indices are (m + n + 1) >> 1 and (m + n + 2) >> 1; for odd length, (m + n + 1) >> 1 and (m + n + 2) >> 1 yield the same results! That’s really clever. With the median index, we find the k-lowest value in a recursion function. Here is the code:

For the brute force solution, with O(m + n) complexity, we keep sorting the two arrays by comparing the current values until we reach the median index: