8000 update 381 · githubniraj/Leetcode@bb83f3f · GitHub
[go: up one dir, main page]
Skip to content

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
8000
Appearance settings

Commit bb83f3f

Browse files
fishercoder1534fishercoder1534
committed
update 381
1 parent d4763a2 commit bb83f3f

File tree

3 files changed

+65
-57
lines changed
  • paginated_contents/algorithms/1st_thousand
  • src
    • main/java/com/fishercoder/solutions/firstthousand
    • test/java/com/fishercoder/firstthousand

3 files changed

+65
-57
lines changed

‎paginated_contents/algorithms/1st_thousand/README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -443,7 +443,7 @@
443443
| 384 | [Shuffle an Array](https://leetcode.com/problems/shuffle-an-array/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_384.java) | | Medium |
444444
| 383 | [Ransom Note](https://leetcode.com/problems/ransom-note/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_383.java) | | Easy | String
445445
| 382 | [Linked List Random Node](https://leetcode.com/problems/linked-list-random-node/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_382.java) | | Medium | Reservoir Sampling
446-
| 381 | [Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_381.java) || Hard |
446+
| 381 | [Insert Delete GetRandom O(1) - Duplicates allowed](https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_381.java) || Hard | Design, Randomized, HashTable
447447
| 380 | [Insert Delete GetRandom O(1)](https://leetcode.com/problems/insert-delete-getrandom-o1/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_380.java) | | Medium | Design, HashMap
448448
| 379 | [Design Phone Directory](https://leetcode.com/problems/design-phone-directory/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_379.java) | | Medium |
449449
| 378 | [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_378.java) | | Medium | Binary Search

‎src/main/java/com/fishercoder/solutions/firstthousand/_381.java

Lines changed: 36 additions & 56 deletions
Original file line numberDiff line numberDiff line change
@@ -1,77 +1,57 @@
11
package com.fishercoder.solutions.firstthousand;
22

3+
import java.util.ArrayList;
34
import java.util.HashMap;
5+
import java.util.LinkedHashSet;
6+
import java.util.List;
47
import java.util.Map;
58
import java.util.Random;
9+
import java.util.Set;
610

711
public class _381 {
812
public static class Solution1 {
9-
10-
Map<Integer, Integer> forwardMap;
11-
//key is the to-be-inserted number, value is its auto-incremented index
12-
Map<Integer, Integer> reverseMap;//the other way around
13-
int index;
14-
Random rand;
15-
1613
/**
17-
* Initialize your data structure here.
14+
* This is a natural extension to the solution from https://leetcode.com/problems/insert-delete-getrandom-o1
15+
* You only need to change the value type of the hashmap to be a set instead of Integer to hold all indexes for this value ever inserted.
1816
*/
19-
public Solution1() {
20-
forwardMap = new HashMap();
21-
reverseMap = new HashMap();
22-
index = 0;
23-
rand = new Random();
24-
}
2517

26-
/**
27-
* Inserts a value to the collection. Returns true if the collection did not already contain the
28-
* specified element.
29-
*/
30-
public boolean insert(int val) {
31-
boolean contains;
32-
if (reverseMap.containsValue(val)) {
33-
contains = true;
34-
} else {
35-
contains = false;
18+
public static class RandomizedCollection {
19+
List<Integer> list;
20+
Map<Integer, Set<Integer>> map;
21+
Random random;
22+
23+
public RandomizedCollection() {
24+
this.list = new ArrayList<>();
25+
this.map = new HashMap<>();
26+
this.random = new Random();
3627
}
37-
forwardMap.put(val,
38-
index);//this will overwrite the preivous key with a new index if the key already exists
39-
reverseMap.put(index, val);
40-
index++;
41-
return contains;
42-
}
4328

44-
/**
45-
* Removes a value from the collection. Returns true if the collection contained the specified
46-
* element.
47-
*/
48-
public boolean remove(int val) {
49-
boolean contains;
50-
if (reverseMap.containsValue(val)) {
51-
contains = true;
52-
if (forwardMap.containsKey(val)) {
53-
int i = forwardMap.get(val);
54-
forwardMap.remove(val);
55-
reverseMap.remove(i);
29+
public boolean insert(int val) {
30+
Set<Integer> indexSet = map.getOrDefault(val, new LinkedHashSet<>());
31+
indexSet.add(list.size());
32+
map.put(val, indexSet);
33+
list.add(val);
34+
return indexSet.size() <= 1;
35+
}
36+
37+
public boolean remove(int val) {
38+
if (!map.containsKey(val) || map.get(val).size() == 0) {
39+
return false;
5640
} else {
57-
//remove the entry in revserve map that has val as its value
58-
reverseMap.values().remove(val);
41+
int removeIndex = map.get(val).iterator().next();
42+
map.get(val).remove(removeIndex);
43+
int lastElement = list.get(list.size() - 1);
44+
list.set(removeIndex, lastElement);
45+
map.get(lastElement).add(removeIndex);
46+
map.get(lastElement).remove(list.size() - 1);
47+
list.remove(list.size() - 1);
48+
return true;
5949
}
60-
} else {
61-
contains = false;
6250
}
63-
return contains;
64-
}
6551

66-
/**
67-
* Get a random element from the collection.
68-
*/
69-
public int getRandom() {
70-
int randNum = rand.nextInt(index);
71-
while (!reverseMap.containsKey(randNum)) {
72-
randNum = rand.nextInt(index);
52+
public int getRandom() {
53+
return list.get(random.nextInt(list.size()));
7354
}
74-
return reverseMap.get(randNum);
7555
}
7656
}
7757
}

‎src/test/java/com/fishercoder/firstthousand/_381Test.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.fishercoder.firstthousand;
2+
3+
import com.fishercoder.solutions.firstthousand._381;
4+
import org.junit.jupiter.api.BeforeEach;
5+
import org.junit.jupiter.api.Test;
6+
7+
import static org.junit.jupiter.api.Assertions.assertFalse;
8+
import static org.junit.jupiter.api.Assertions.assertTrue;
9+
10+
public class _381Test {
11+
private static _381.Solution1.RandomizedCollection randomizedCollection;
12+
13+
@BeforeEach
14+
public void setup() {
15+
randomizedCollection = new _381.Solution1.RandomizedCollection();
16+
}
17+
18+
@Test
19+
public void test1() {
20+
assertTrue(randomizedCollection.insert(1));
21+
assertFalse(randomizedCollection.insert(1));
22+
assertTrue(randomizedCollection.insert(2));
23+
randomizedCollection.getRandom();
24+
assertTrue(randomizedCollection.remove(2));
25+
randomizedCollection.getRandom();
26+
}
27+
28+
}

0 commit comments

Comments
 (0)
0