# Inspired by leetcode 380 RandomizedSet

• 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;
}
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()));
}
}
``````

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