Shuffle a set of numbers without duplicates.
Example:
// Init an array with set 1, 2, and 3. int[] nums = {1,2,3}; Solution solution = new Solution(nums); // Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned. solution.shuffle(); // Resets the array back to its original configuration [1,2,3]. solution.reset(); // Returns the random shuffling of array [1,2,3]. solution.shuffle();
解法一:
public class Solution {
private int[] nums;
private Random random;
public Solution(int[] nums) {
this.nums = nums;
random = new Random();
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
return nums;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
if(nums == null) return null;
int[] a = nums.clone();
for(int j = 1; j < a.length; j++) {
int i = random.nextInt(j + 1);
swap(a, i, j);
}
return a;
}
private void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
解法2: 提前generate所有permutations,然后每次任意取一个。
如果用完一个,这次shuffle不能再用的话,就搞一下index array
但是超时!!!
public class Solution {
int[] indices;
int end;
Random rand;
List<List<Integer>> candidates;
public Solution(int[] nums) {
int n = nums.length;
rand = new Random();
candidates = new ArrayList<>();
candidates.add(new ArrayList<>());
for(int i = 0; i < n; i++){
int size = candidates.size();
for(int j = 0; j < size;j++){
List<Integer> list = candidates.remove(0);
for(int k = 0; k < list.size();k++){
list.add(k,nums[i]);
candidates.add(new ArrayList<>(list));
list.remove(k);
}
list.add(nums[i]);
candidates.add(new ArrayList<>(list));
}
}
end = candidates.size()-1;
indices = new int[candidates.size()];
for(int i = 0; i < candidates.size(); i++)
indices[i] = i;
}
/** Resets the array to its original configuration and return it. */
public int[] reset() {
int n = indices.length;
for(int i = 0; i < n; i++)
indices[i] = i;
end = --n;
int[] ans = new int[candidates.get(end).size()];
int k = 0;
for(int num: candidates.get(end))
ans[k++] = num;
return ans;
}
/** Returns a random shuffling of the array. */
public int[] shuffle() {
if(end == -1) reset();
int i = rand.nextInt(end+1);
int idx = indices[i];
swap(indices, end, i);
end--;
int[] ans = new int[candidates.get(idx).size()];
int k = 0;
for(int num: candidates.get(idx))
ans[k++] = num;
return ans;
}
public void swap(int[] A, int i, int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(nums);
* int[] param_1 = obj.reset();
* int[] param_2 = obj.shuffle();
*/
没有评论:
发表评论