A simple solution is to create an auxiliary array temp[] which is initially a copy of arr[].
Randomly select an element from temp[], copy the randomly selected element to arr[0] and remove the selected element from temp[].
Repeat the same process n times and keep copying elements to arr[1], arr[2], … . The time complexity of this solution will be O(n^2).
T: O(n^2)
public int[] shuffle() {
List<Integer> aux = getArrayCopy();
for (int i = 0; i < array.length; i++) { // O(n)
int removeIdx = rand.nextInt(aux.size());
array[i] = aux.get(removeIdx);
aux.remove(removeIdx); // this is also O(n)
}
return array;
}
use fisher yates shuffle algorithm
refer:
T:O(n)
S:O(n)
class Solution {
int[] nums;
Random rand;
public Solution(int[] nums) {
this.nums = nums;
this.rand = new Random();
}
// The solution expects that we always use
// " the original array " to shuffle() else some of the test cases fail
// because this q needs reset to nums, so we need keep nums
public int[] reset() {
return this.nums;
}
public int[] shuffle() {
int[] clone = nums.clone();
for (int i = nums.length - 1; i > 0; i--) {
int j = rand.nextInt(i+1);
int temp = clone[i];
clone[i] = clone[j];
clone[j] = temp;
}
return clone;
}
}
/**
* 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();
*/
latest explain
class Solution {
private int nums[];
private Random rand = new Random();
public Solution(int[] nums) {
this.nums = nums;
}
public int[] reset() {
return this.nums;
}
public int[] shuffle() {
int[] clone = nums.clone();
int n = clone.length;
for (int i = n - 1; i > 0; i--) {
int pickIdx = rand.nextInt(i+1); //
int temp = clone[i];
clone[i] = clone[pickIdx];
clone[pickIdx] = temp;
}
return clone;
}
}
/**
* 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();
fisher-yates
random()
i from end (n-1) i > 0
// random.nextInt(2) -> will generate 0~1
random pik a poistion (0~n-1), do swap
n-1 swap with random [0~n-1]
n-2 swap with random [0~n-2]
..
1 swap with random [0~1]
T: O(n)
S: O(n), this q needs keep original array
*/
ex:
so you can see the index and rand index maybe the same, means don't move
ex:["Solution","shuffle","reset","shuffle"]
[[[1,2,3]],[],[],[]]
// i= 2 => 2+1 => 0~2
i from 2 to 1, (0 不換
i = 2 swap for all elements （0~2
i = 1 swap for 0~1
