Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.HashMap;
- import java.util.Random;
- /**
- * Using a ArrayList and HashMap
- *
- * Time Complexity: All function have average O(1)
- *
- * Space Complexity: O(N)
- *
- * N = Number of values currently stored in the data structure.
- */
- class RandomizedSet {
- ArrayList<Integer> nums;
- HashMap<Integer, Integer> map;
- Random rand;
- /** Initialize your data structure here. */
- public RandomizedSet() {
- nums = new ArrayList<>();
- map = new HashMap<>();
- rand = new Random();
- }
- /**
- * Inserts a value to the set. Returns true if the set did not already contain
- * the specified element.
- */
- public boolean insert(int val) {
- if (map.containsKey(val)) {
- return false;
- }
- nums.add(val);
- map.put(val, nums.size() - 1);
- return true;
- }
- /**
- * Removes a value from the set. Returns true if the set contained the specified
- * element.
- */
- public boolean remove(int val) {
- if (!map.containsKey(val)) {
- return false;
- }
- int index = map.get(val);
- if (index != nums.size() - 1) {
- // Put the current last value at the index of the value to be removed.
- int lastVal = nums.get(nums.size() - 1);
- nums.set(index, lastVal);
- map.put(lastVal, index);
- }
- nums.remove(nums.size() - 1);
- map.remove(val);
- return true;
- }
- /** Get a random element from the set. */
- public int getRandom() {
- return nums.get(rand.nextInt(nums.size()));
- }
- }
- /**
- * Your RandomizedSet object will be instantiated and called as such:
- * RandomizedSet obj = new RandomizedSet(); boolean param_1 = obj.insert(val);
- * boolean param_2 = obj.remove(val); int param_3 = obj.getRandom();
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement