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


  • 0
    X

    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;
        }
        set.add(val);
        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 mask = Integer.MIN_VALUE;
            while(mask != 0){
                int bit = (num & mask) != 0 ? 1 : 0;
                current.children[bit].prefix--;
                current = current.children[bit];
                mask >>>= 1;
            }
        }
        
        public int getRandom(int total){
            int result = 0;
            int mask = Integer.MIN_VALUE;
            TrieNode current = root;
            int random = rd.nextInt(total) + 1;
            while(mask != 0){
                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;
                    result |= mask;
                }
                mask >>>= 1;
            }
            return result;
        }
        
        public void insert(int num){
            TrieNode current = root;
            int mask = Integer.MIN_VALUE;
            while(mask != 0){
                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];
                mask >>>= 1;
            }
        }
        public static class TrieNode{
            TrieNode[] children;
            int prefix;
            public TrieNode (){
                children = new TrieNode[2];
                prefix = 0;
            }
        }
    }
    

    }


  • 0
    S

    damn son!
    Pretty interesting approach.


Log in to reply
 

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