Java Solution + array + hashmap + index pointer


  • 0
    J

    Changed from delete to remove. Basically, the idea is to keep track of the last index so that get random is just like to generate a random integer from 0 to the end. The trick is during a deletion, you put the last index of the array to that position.

    public class RandomizedSet {
        HashMap<Integer,Integer> map;
        int [] array;
        int cur;
        /** Initialize your data structure here. */
        public RandomizedSet() {
            map = new HashMap<>();
            array = new int [100];
            cur = 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(cur == array.length){
                int size = 2 * array.length;
                int [] temp = new int [size];
                for(int i = 0; i < array.length; i++)
                    temp[i] = array[i];
                array = temp;
            }
            if(map.containsKey(val))
                return false;
            array[cur++] = val;
            map.put(val, cur - 1);
            return true;
        }
        
        /** Deletes a value from the set. Returns true if the set contained the specified element. */
        public boolean remove(int val) {
            if(!map.containsKey(val))
                return false;
            int index = map.get(val);
            int lastIndex = --cur;
            if(lastIndex >= 0)
                array[index] = array[lastIndex];
            map.put(array[lastIndex], index);
            map.remove(val);
            return true;
        }
        
        /** Get a random element from the set. */
        public int getRandom() {
            int index = (int)Math.random() * cur;
            return array[index];
        }
    }
    

  • 0

    @jessexu You can import Random package yourself by adding import java.util.Random; in the beginning of your code. We will probably add the import automatically for you later, but for now this is a workaround.


  • 0

    NICE
    Or use a double linked list


  • 0
    C

    Nice idea! Here is accepted Java solution using similar idea.

    import java.util.Random;

    public class RandomizedSet {

    int lastIndex;
    Map<Integer, Integer> map;
    List<Integer> list;
    Random random;
    
    /** Initialize your data structure here. */
    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        random = new Random();
    }
    
    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        boolean ret = !map.containsKey(val);
        if(ret) { 
            map.put(val, lastIndex);
            list.add(val);
            lastIndex++;
        }
        return ret;
    }
    
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        boolean ret = map.containsKey(val);
        if(ret){
            int index = map.remove(val);
            int lastElement = list.get(list.size()-1);
            if(val!=lastElement){
            	map.put(lastElement, index);
            	list.set(index, lastElement);
            }
            list.remove(list.size()-1);
            lastIndex--;
        }
        return ret;
    }
    
    /** Get a random element from the set. */
    public int getRandom() {
        int randomIndex = random.nextInt(lastIndex);
        return list.get(randomIndex);
    }
    

    }

    /**

    • 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

    @三千世界 said in Java Solution + array + hashmap + index pointer:

    Or use a double linked list

    How would that work?


Log in to reply
 

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