Java HashMap and List


  • 0
    V
    import java.util.*;
    public class RandomizedSet 
    {
        HashMap<Integer, Integer> hm;
        List<Integer> ml;
        int ind;
        Random i;
        /** Initialize your data structure here. */
        public RandomizedSet() 
        {
            ind = 0;
            i = new Random();
            hm = new HashMap<Integer, Integer>();
            ml = new ArrayList<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(hm.containsKey(val))
                return false;
            hm.put(val, ind);
            ml.add(ind, val);
            ind++;
            return true;
        }
        
        /** Removes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) 
        {
            if(!hm.containsKey(val))
                return false;
            int i = hm.get(val);
            hm.remove(val);
            ind--;
            if(ind != i)
            {
                hm.put(ml.get(ind), i);
                ml.set(i, ml.get(ind));
            }
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() 
        {
            return ml.get(i.nextInt(ind));
        }
    }
    
    /**
     * 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();
     */

  • 0
    C

    Very smart solution. I was thinking to create the double linked list by myself, just like we did for the LRC (Least Recent Cache) question.

    Your solution can use the ArrayList which is very smart.

    The only issue I found is that you forgot to delete the node in the List after removing it in the HashMap.

        public boolean remove(int val) 
        {
            if(!hm.containsKey(val))
                return false;
            int i = hm.get(val);
            hm.remove(val);
            ind--;
            if(ind != i)
            {
                hm.put(ml.get(ind), i);
                ml.set(i, ml.get(ind));
            }
            ml.remove(ind);
            return true;
        }
    

  • 0
    V

    Thank you. Well, I thought the array resizing (increase/decrease) in Java would take some time - depending on the operations, so instead let the array be as is, and save some time :) ..
    But yes, should consider that to save memory.


  • 0
    Q

    Here is mine HashMap + ArrayList solution

    public class RandomizedSet {
        private List<Integer> list = new ArrayList<>();
        private Map<Integer, Integer> valToIndex = new HashMap<>();
        java.util.Random r = new java.security.SecureRandom();
        public RandomizedSet() {}
        public boolean insert(int val) {
            if (valToIndex.get(val)!=null)
                return false;
            list.add(val);
            valToIndex.put(val, list.size()-1);
            return true;
        }
        public boolean remove(int val) {
            Integer index = valToIndex.get(val);
            int lastIndex = list.size()-1;
            if (index == null)
                return false;
            if (index != lastIndex){
                int lastVal = list.get(lastIndex);
                valToIndex.put(lastVal, index);
                list.set(index, lastVal);
            }
            valToIndex.remove(val);
            list.remove(lastIndex);
            return true;
        }
        public int getRandom() {
            return list.get(r.nextInt(list.size()));
        }
    }
    

Log in to reply
 

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