未分類

Insert Delete GetRandom O(1)

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回傳對應的資料即可。

分享到