Why do I pass the getRandom() test randomly?


  • 0
    L

    Here is my code. I submitted the code three times and it passed for one time.
    The other two fails the getRandom test. After that I submitted again and it passed the test.
    I am not sure what is wrong with my code here.
    Can someone help me?

    public class RandomizedSet {
        private List<Integer>[] HashLists;
        private int loadFactor = 2;
        private int size;
        /** Initialize your data structure here. */
        public RandomizedSet() {
            HashLists = new List[20];
            size = 0;
            for(int i = 0; i < 20; i++) {
                HashLists[i] = new LinkedList<Integer>();
            }
        }
        private void resize() {
            List[] newLists = new List[size * 2];
            for(int i = 0; i < newLists.length; i++) {
                newLists[i] = new LinkedList<Integer>();
            }
            for (int i = 0; i < HashLists.length; i++) {
                List<Integer> cur = HashLists[i];
                while(cur.size() != 0) {
                    int x = cur.remove(0);
                    int num = x % newLists.length;
                    while (num < 0) num = (num + newLists.length) % newLists.length;           
                    newLists[num].add(x);
                }
            }
            HashLists = newLists;
        }
        /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
        public boolean insert(int val) {
            if (size + 1 > loadFactor * HashLists.length) resize();
            int num = val % HashLists.length;
            while (num < 0) num = (num + HashLists.length) % HashLists.length;
            
            if (!HashLists[num].contains(val)) {
                size++;
                HashLists[num].add(val);
                return true;
            }
            return false;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            // if (size - 1 < 0.25 * HashLists.length) resize();
            int num = val % HashLists.length;
            while (num < 0) num = (num + HashLists.length) % HashLists.length;
            
            if (HashLists[num].remove((Object) val)) {
                size--;
                return true;
            }
            return false;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            Random rand = new Random();
            int n = rand.nextInt(HashLists.length);
            while(HashLists[n].size() == 0) n = rand.nextInt(HashLists.length);
            int m = rand.nextInt(HashLists[n].size());
            return HashLists[n].get(m);        
        }
    }
    

Log in to reply
 

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