384. Shuffle an Array

brute force

https://www.geeksforgeeks.org/shuffle-a-given-array-using-fisher-yates-shuffle-algorithm/

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:

Shuffle a given array using Fisher–Yates shuffle Algorithm - GeeksforGeeksGeeksforGeeks

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

i:2,pickIdx:2
i:1,pickIdx:1
i:2,pickIdx:0
i:1,pickIdx:0

 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