384. Shuffle an Array

三刷 07/2022

Version #1 Randomly swap

Time O(N)

Space O(N)

Runtime: 75 ms, faster than 74.21% of Java online submissions for Shuffle an Array.

Memory Usage: 65.6 MB, less than 64.08% of Java online submissions for Shuffle an Array.

class Solution {

    int[] arr;

    Random rd;

    public Solution(int[] nums) {

        this.arr = nums;

        this.rd = new Random();

    }

    

    public int[] reset() {

        return arr;

    }

    

    public int[] shuffle() {

        int[] nums = arr.clone();

        for (int i = nums.length - 1; i >= 0; i--) {

            int j = rd.nextInt(i + 1);

            // System.out.printf("i=%d,j=%d\n", i, j);

            swap(nums, i, j);

        }

        return nums;

    }

    

    private void swap(int[] nums, int i, int j) {

        if (i == j) {

            return;

        }

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

/**

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

 */

二刷 06/2022

Version #1 Randomly swap

重点是nextInt的时候一定是nextInt(i + 1)因为也有概率和自己swap

同时nums.clone对于primitive type是deep copy对于object是shallow copy

Time O(N)

Space O(N)

Runtime: 54 ms, faster than 85.79% of Java online submissions for Shuffle an Array.

Memory Usage: 48 MB, less than 94.38% of Java online submissions for Shuffle an Array.

class Solution {

    private int[] originalNums;

    public Solution(int[] nums) {

        originalNums = nums;

    }

    

    public int[] reset() {

        int[] copy = originalNums.clone();

        return copy;

    }

    

    public int[] shuffle() {

        int[] copy = originalNums.clone();

        Random rd = new Random();

        for (int i = copy.length - 1; i > 0; i--) {

            int j = rd.nextInt(i + 1);

            int temp = copy[i];

            copy[i] = copy[j];

            copy[j] = temp;

        }

        return copy;

    }

}

/**

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

 */

一刷
92.78 %
class Solution {
    int[] nums;
    public Solution(int[] nums) {
        this.nums = nums;
    }
   
    /** 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[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            result[i] = nums[i];
        }
        Random rd = new Random();
        for (int i = result.length - 1; i > 0; i--) {
            int index = rd.nextInt(i + 1); // randomly pick a number from [0, i]
            int temp = result[index];
            result[index] = result[i];
            result[i] = temp;
           
        }
        return result;
    }
}