Solution in Java using Trie, not fastest nor simplest, but interesting

• public class RandomizedSet {

Trie dataStore;
HashSet<Integer> set;

/** Initialize your data structure here. */
public RandomizedSet() {
dataStore = new Trie();
set = new HashSet<Integer>();
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if(set.contains(val)){
return false;
}
dataStore.insert(val);
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if(!set.contains(val)){
return false;
}
set.remove(val);
dataStore.delete(val);
return true;
}

/** Get a random element from the set. */
public int getRandom() {
return dataStore.getRandom(set.size());
}

public static class Trie{
TrieNode root;
Random rd;

public Trie(){
root = new TrieNode();
rd = new Random();
}

public void delete(int num){
TrieNode current = root;
int bit = (num & mask) != 0 ? 1 : 0;
current.children[bit].prefix--;
current = current.children[bit];
}
}

public int getRandom(int total){
int result = 0;
TrieNode current = root;
int random = rd.nextInt(total) + 1;
int zeros = current.children[0] != null? current.children[0].prefix : 0;
int ones = current.children[1] != null? current.children[1].prefix : 0;
if(random <= zeros){
current = current.children[0];

} else {
current = current.children[1];
random -= zeros;
}
}
return result;
}

public void insert(int num){
TrieNode current = root;
int bit = (num & mask) != 0 ? 1 : 0;
if(current.children[bit] == null){
current.children[bit] = new TrieNode();
}
current.children[bit].prefix++;
current = current.children[bit];
}
}
public static class TrieNode{
TrieNode[] children;
int prefix;
public TrieNode (){
children = new TrieNode[2];
prefix = 0;
}
}
}

}

• damn son!
Pretty interesting approach.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.