Inspired by leetcode 380 RandomizedSet


  • 0
    D

    Create an index array first. Then randomly pick one index. Every result's probability is 1/n * 1/(n-1) * 1/(n-2) * ... 1/1, which is exactly the inverse of total number of permutations.

    public class Solution {
        
        private int[] nums;
    
        public Solution(int[] nums) {
            this.nums = nums;
        }
        
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
            return this.nums;
        }
        
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
            RandomizedSet set = new RandomizedSet();
            for (int i = 0; i < nums.length; i++) {
                set.insert(i);
            }
            int[] ret = new int[nums.length];
            for (int i = 0; i < nums.length; i++) {
                int r = set.getRandom();
                ret[i] = nums[r];
                set.remove(r);
            }
            return ret;
        }
    }
    
    class RandomizedSet {
        
        private Map<Integer, Integer> map = new HashMap<>();
        private List<Integer> array = new ArrayList<>();
    
        /** Initialize your data structure here. */
        public RandomizedSet() {
            
        }
        
        /** 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;
            }
            array.add(val);
            map.put(val, array.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)) {
                return false;
            }
            if (map.get(val) != array.size() - 1) {
                map.put(array.get(array.size() - 1), map.get(val));
                array.set(map.get(val), array.get(array.size() - 1));
            }
            map.remove(val);
            array.remove(array.size() - 1);
            return true;
        }
        
        private java.util.Random r = new java.util.Random();
        
        /** Get a random element from the set. */
        public int getRandom() {
            return array.get(r.nextInt(array.size()));
        }
    }
    

Log in to reply
 

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