LeetCode: Insert Delete GetRandom O(1) – Duplicates allowed

Posted on January 16, 2018July 26, 2020 by braindenny

Insert Delete GetRandom O(1) – Duplicates allowed

Similar Problems:

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.

Example:

// Init an empty collection.
RandomizedCollection collection = new RandomizedCollection();

// Inserts 1 to the collection. Returns true as the collection did not contain 1.
collection.insert(1);

// Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
collection.insert(1);

// Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
collection.insert(2);

// getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
collection.getRandom();

// Removes 1 from the collection, returns true. Collection now contains [1,2].
collection.remove(1);

// getRandom should return 1 and 2 both equally likely.
collection.getRandom();

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Solution: hashmap with set as value

// https://code.dennyzhang.com/insert-delete-getrandom-o1-duplicates-allowed
// Basic Ideas: hashmap + array
//
// Complexity: Time O(1), Space O(n)
import "math/rand"
type RandomizedCollection struct {
    // value to positions
    positions map[int]map[int]bool
    values []int
}

/** Initialize your data structure here. */
func Constructor() RandomizedCollection {
    return RandomizedCollection{positions:map[int]map[int]bool{}, values:[]int{}}
}

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
func (this *RandomizedCollection) Insert(val int) bool {
    res := false
    if _, ok := this.positions[val]; !ok {
        this.positions[val] = map[int]bool{}
        res = true
    }
    this.positions[val][len(this.values)] = true
    this.values = append(this.values, val)
    return res
}

/** Removes a value from the collection. Returns true if the collection contained the specified element. */
func (this *RandomizedCollection) Remove(val int) bool {
    // not found
    _, ok := this.positions[val]
    if !ok || len(this.positions[val]) == 0 {
        return false
    }
    // get one random position for the value of val
    pos := -1
    for k, _ := range this.positions[val] {
        pos = k
        delete(this.positions[val], pos)
        break
    }
    // move last_element to val
    last_element := this.values[len(this.values)-1]
    this.values[pos] = last_element

    this.positions[last_element][pos] = true
    delete(this.positions[last_element], len(this.values)-1)

    // shorten array
    this.values = this.values[0:len(this.values)-1]
    return true
}

/** Get a random element from the collection. */
func (this *RandomizedCollection) GetRandom() int {
    index := rand.Intn(len(this.values))
    return this.values[index]
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

Post Views: 5