Java solution using HashMap && ArrayList


  • 0
    U
    public class RandomizedSet {
        
        Map<Integer, Integer> map;
        List<Integer> list;
        int index;
        Random rand = new Random();
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<>();
            list = new ArrayList<>();
            index = 0;
        }
        
        /** 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;
            } else {
                list.add(val);
                map.put(val, list.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)) {
                int i = map.get(val);
                int last = list.get(list.size() - 1);
                map.put(last, i);
                swap(i, list.size() - 1);
                map.remove(val);
                list.remove(list.size() - 1);
                return true;
            } else {
                return false;
            }
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            int index = rand.nextInt(list.size());
            return list.get(index);
        }
        
        private void swap(int i, int j) {
            int temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
    }
    
    /**
     * 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();
     */

Log in to reply
 

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