LeetCode - Algorithms - 384. Shuffle an Array

It seemed that Spotify only let you click big green SHUFFLE PLAY button if you are not premium user.

Java

1 - Fisher–Yates shuffle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Random;

class Solution {
	private int[] shuffleArr;
	private int[] originalArr;    

    public Solution(int[] nums) {
    	originalArr = nums.clone();
    	shuffleArr = nums.clone();       
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	Random random = new Random();
    	int temp = 0;
    	int randomPosition = 0;
    	final int N = shuffleArr.length;
    	for(int i=shuffleArr.length-1;i>0;i--) {
    		randomPosition = random.nextInt(N);
    		temp = shuffleArr[i];
    		shuffleArr[i] = shuffleArr[randomPosition];
    		shuffleArr[randomPosition] = temp;
    	}
        return shuffleArr;
    }
}

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 210 ms
  • Your runtime beats 38.29 % of java submissions.

2 the Knuth (or Fisher-Yates) shuffling algorithm

© Robert Sedgewick and Kevin Wayne

Proposition. [Fisher-Yates 1938] Knuth shuffling algorithm produces a uniformly random permutation of the input array in linear time.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    private int[] shuffleArr;
    private int[] originalArr;
    
    public Solution(int[] nums) {
        originalArr = nums.clone();
        shuffleArr = nums.clone();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        final int N = shuffleArr.length;
        int swap;
        for (int i = 0; i < N; i++) {
            int r = (int) (Math.random() * (i + 1));
            swap = shuffleArr[r];
            shuffleArr[r] = shuffleArr[i];
            shuffleArr[i] = swap;
        }
        return shuffleArr;
    }
}

/**
 * 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();
 */

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 76 ms, faster than 76.75% of Java online submissions for Shuffle an Array.
  • Memory Usage: 47.2 MB, less than 6.24% of Java online submissions for Shuffle an Array.

3 - Collections.shuffle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
	private Integer[] shuffleArr;
	private int[] originalArr;    

    public Solution(int[] nums) {
    	shuffleArr = new Integer[nums.length];
    	for(int i=0;i<nums.length;i++)
    		shuffleArr[i] = nums[i];
    	originalArr = nums.clone();       
    }

    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        return originalArr;
    }

    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
    	List<Integer> list = Arrays.asList(shuffleArr);
    	Collections.shuffle(list);
    	Integer[] a = new Integer[shuffleArr.length];
    	list.toArray(a);
    	int[] r = new int[a.length];
    	for(int i=0;i<a.length;i++)
    		r[i] = a[i];
        return r;        
    }
}

Submission Detail

  • 10 / 10 test cases passed.
  • Runtime: 141 ms
  • Your runtime beats 96.48 % of java submissions.

ref