未分類

Insert Delete GetRandom O(1)

Array, Design, Go, HashTable, LeetCode

Insert Delete GetRandom O(1)

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

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

For example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();
// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);
// Returns false as 2 does not exist in the set.
randomSet.remove(2);
// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);
// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();
// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);
// 2 was already in the set, so return false.
randomSet.insert(2);
// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
提示 解題應用
HashTable HashMap

Default:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type RandomizedSet struct {
    
}
/** Initialize your data structure here. */
func Constructor() RandomizedSet {
    
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
func (this *RandomizedSet) Insert(val int) bool {
    
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
func (this *RandomizedSet) Remove(val int) bool {
    
}
/** Get a random element from the set. */
func (this *RandomizedSet) GetRandom() int {
    
}
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Insert(val);
 * param_2 := obj.Remove(val);
 * param_3 := obj.GetRandom();
 */

解答思路:

如果要儲存、刪除及查找資料，並且都在時間複雜度O(1)完成的話，那麼當然馬上就會想到要用hashmap來儲存資料，不過唯一的問題是隨機取出資料時(所有資料取出的機率皆相等)，也要在時間複雜度O(1)完成，在hashmap儲存中需要key才能取出value，而key又不像陣列的index值一樣能夠確定範圍，因此為了能夠順利隨機取出hashmap的資料，總共需要兩個hashmap來儲存同一份資料，一個是儲存資料與index的對應關係，另一個則是儲存index與資料的對應關係，當然每次新增資料時index的值就需要我們自行計算並賦予，而在移除資料時除了從兩份hashmap移除之外，要記得將最後index的資料移至有空缺的位置，好比移除了index為4的資料就將index最大值的資料移至4，如此一來全部資料的index範圍就能維持在[0~資料長度-1]之間而中間不會有空缺，最後當要隨機取出資料時，只要產生正值的隨機數與資料長度取餘數，其值做為index回傳對應的資料即可。

程式碼解說:

既然需要兩個hashmap來儲存同一份資料，當然在初始化的時就指派兩個hashmap來做儲存，其中一個是儲存資料與index的對應關係，另一個則是儲存index與資料的對應關係

1
2
3
4
5
6
7
type RandomizedSet struct {
	numIndex map[int]int
	indexNum map[int]int
}
func Constructor() RandomizedSet {
	return RandomizedSet{make(map[int]int), make(map[int]int)}
}

接著在新增資料的時候，先檢查該資料是否已存在於hashmap之中(資料對應到index的hashmap)，如果存在就直接回傳false，否則才新增資料至兩個hashmap之中，而新資料的index值就正好是目前資料的長度，新增完畢之後才回傳true

1
2
3
4
5
6
7
8
9
10
func (this *RandomizedSet) Insert(val int) bool {
	_, ok := this.numIndex[val]
	if !ok {
		index := len(this.numIndex)
		this.numIndex[val] = index
		this.indexNum[index] = val
		return true
	}
	return false
}

而在移除資料的時候，一樣也是先檢查該資料是否已存在於hashmap之中，如果不存在就直接回傳false，否則才將資料從兩個hashmap之中移除，接著再檢查最後index的資料(刪除後最後的index是全部資料的長度;如果是刪除前取則是要將長度-1)是否存在，如果存在就將最後一筆資料移至刪除後產生的空缺位置(記得最後index對應到的資料在hashmap中要完全移除，至於資料對應到的最後index則用先前空缺的index取代即可)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (this *RandomizedSet) Remove(val int) bool {
	index, ok := this.numIndex[val]
	if ok {
		delete(this.numIndex, val)
		delete(this.indexNum, index)
		num, exist := this.indexNum[len(this.numIndex)]
		if exist {
			delete(this.indexNum, len(this.numIndex))
			this.numIndex[num] = index
			this.indexNum[index] = num
		}
		return true
	}
	return false
}

前面兩個新增與刪除的函數如此費功夫，正是為了在最後要隨機取出資料時能夠變的非常容易，此時就只要產生正值的隨機數與資料長度取餘數，其值做為index回傳對應的資料即可(在index對應到資料的hashmap)

1
2
3
func (this *RandomizedSet) GetRandom() int {
	return this.indexNum[(rand.Int())%len(this.numIndex)]
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
type RandomizedSet struct {
	numIndex map[int]int
	indexNum map[int]int
}
func Constructor() RandomizedSet {
	return RandomizedSet{make(map[int]int), make(map[int]int)}
}
func (this *RandomizedSet) Insert(val int) bool {
	_, ok := this.numIndex[val]
	if !ok {
		index := len(this.numIndex)
		this.numIndex[val] = index
		this.indexNum[index] = val
		return true
	}
	return false
}
func (this *RandomizedSet) Remove(val int) bool {
	index, ok := this.numIndex[val]
	if ok {
		delete(this.numIndex, val)
		delete(this.indexNum, index)
		num, exist := this.indexNum[len(this.numIndex)]
		if exist {
			delete(this.indexNum, len(this.numIndex))
			this.numIndex[num] = index
			this.indexNum[index] = num
		}
		return true
	}
	return false
}
func (this *RandomizedSet) GetRandom() int {
	return this.indexNum[(rand.Int())%len(this.numIndex)]
}

總結:

如果要儲存、刪除及查找資料，並且都在時間複雜度O(1)完成的話，那麼當然馬上就會想到要用hashmap來儲存資料，不過如果還要隨機取出資料時(所有資料取出的機率皆相等)，也要在時間複雜度O(1)完成的話，就需要兩個hashmap來儲存同一份資料，一個是儲存資料與index的對應關係，另一個則是儲存index與資料的對應關係，每次新增資料時index的值就需要我們自行計算並賦予，而在移除資料時除了從兩份hashmap移除之外，要記得將最後index的資料移至有空缺的位置，如此一來全部資料的index範圍就能維持在[0~資料長度-1]之間而中間不會有空缺，最後當要隨機取出資料時，只要產生正值的隨機數與資料長度取餘數，其值做為index回傳對應的資料即可。

分享到