Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/384.html

Given an integer array nums, design an algorithm to randomly shuffle the array. All permutations of the array should be equally likely as a result of the shuffling.

Implement the Solution class:

  • Solution(int[] nums) Initializes the object with the integer array nums.
  • int[] reset() Resets the array to its original configuration and returns it.
  • int[] shuffle() Returns a random shuffling of the array.

 

Example 1:

Input
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
Output
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

Explanation
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // Shuffle the array [1,2,3] and return its result.
                       // Any permutation of [1,2,3] must be equally likely to be returned.
                       // Example: return [3, 1, 2]
solution.reset();      // Resets the array back to its original configuration [1,2,3]. Return [1, 2, 3]
solution.shuffle();    // Returns the random shuffling of array [1,2,3]. Example: return [1, 3, 2]

 

Constraints:

  • 1 <= nums.length <= 50
  • -106 <= nums[i] <= 106
  • All the elements of nums are unique.
  • At most 104 calls in total will be made to reset and shuffle.

Algorithm

Traverse each position of the array, randomly generate a coordinate position each time, and then exchange the number of the current traverse position and the randomly generated coordinate position.

If the array has n numbers, then we also randomly exchange n sets of positions, thus achieving the purpose of shuffling.

It should be noted here that i + rand()% (res.size()-i) cannot be written as rand()% res.size().

Code

  • import java.util.ArrayList;
    import java.util.List;
    import java.util.Random;
    
    public class Shuffle_an_Array {
    
        // 1. array deep copy
        // 2. random.nextInt to dynamic list size
        class Solution {
            private int[] array;
            private int[] original;
    
            private Random rand = new Random();
    
            private List<Integer> getArrayCopy() {
                List<Integer> asList = new ArrayList<Integer>();
                for (int i = 0; i < array.length; i++) {
                    asList.add(array[i]);
                }
                return asList;
            }
    
            public Solution(int[] nums) {
                array = nums;
                original = nums.clone();
            }
    
            public int[] reset() {
                array = original;
                original = original.clone();
                return array;
            }
    
            public int[] shuffle() {
                List<Integer> aux = getArrayCopy();
    
                for (int i = 0; i < array.length; i++) {
                    int removeIdx = rand.nextInt(aux.size());
                    array[i] = aux.get(removeIdx);
                    aux.remove(removeIdx);
                }
    
                return array;
            }
        }
    /**
     * 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();
     */
    }
    
    ############
    
    class Solution {
        private int[] nums;
        private int[] original;
        private Random rand;
    
        public Solution(int[] nums) {
            this.nums = nums;
            this.original = Arrays.copyOf(nums, nums.length);
            this.rand = new Random();
        }
    
        public int[] reset() {
            nums = Arrays.copyOf(original, original.length);
            return nums;
        }
    
        public int[] shuffle() {
            for (int i = 0; i < nums.length; ++i) {
                swap(i, i + rand.nextInt(nums.length - i));
            }
            return nums;
        }
    
        private void swap(int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }
    
    /**
     * 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();
     */
    
  • // OJ: https://leetcode.com/problems/shuffle-an-array/
    // Time:
    //      Solution: O(N)
    //      reset: O(1)
    //      shuffle: O(N)
    // Space: O(N)
    class Solution {
    private:
        vector<int> nums;
    public:
        Solution(vector<int> nums) : nums(nums) {}
        
        vector<int> reset() {
            return nums;
        }
        
        vector<int> shuffle() {
            vector<int> ans(nums);
            for (int i = nums.size(); i > 1; --i) {
                int j = rand() % i;
                swap(ans[i - 1], ans[j]);
            }
            return ans;
        }
    };
    
  • class Solution:
        def __init__(self, nums: List[int]):
            self.nums = nums
            self.original = nums.copy()
    
        def reset(self) -> List[int]:
            self.nums = self.original.copy()
            return self.nums
    
        def shuffle(self) -> List[int]:
            for i in range(len(self.nums)):
                j = random.randrange(i, len(self.nums))
                self.nums[i], self.nums[j] = self.nums[j], self.nums[i]
            return self.nums
    
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(nums)
    # param_1 = obj.reset()
    # param_2 = obj.shuffle()
    
    ############
    
    class Solution(object):
    
      def __init__(self, nums):
        """
    
        :type nums: List[int]
        :type size: int
        """
        self.nums = nums
        self.reset = lambda: self.nums
    
      def shuffle(self):
        """
        Returns a random shuffling of the array.
        :rtype: List[int]
        """
        nums = self.nums + []
        for i in reversed(range(0, len(nums))):
          idx = random.randrange(0, i + 1)
          nums[i], nums[idx] = nums[idx], nums[i]
        return nums
    
    # Your Solution object will be instantiated and called as such:
    # obj = Solution(nums)
    # param_1 = obj.reset()
    # param_2 = obj.shuffle()
    
    
  • type Solution struct {
    	nums, original []int
    }
    
    func Constructor(nums []int) Solution {
    	return Solution{nums, append([]int(nil), nums...)}
    }
    
    func (this *Solution) Reset() []int {
    	copy(this.nums, this.original)
    	return this.nums
    }
    
    func (this *Solution) Shuffle() []int {
    	n := len(this.nums)
    	for i := range this.nums {
    		j := i + rand.Intn(n-i)
    		this.nums[i], this.nums[j] = this.nums[j], this.nums[i]
    	}
    	return this.nums
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * obj := Constructor(nums);
     * param_1 := obj.Reset();
     * param_2 := obj.Shuffle();
     */
    
  • class Solution {
        private nums: number[];
    
        constructor(nums: number[]) {
            this.nums = nums;
        }
    
        reset(): number[] {
            return this.nums;
        }
    
        shuffle(): number[] {
            const n = this.nums.length;
            const res = [...this.nums];
            for (let i = 0; i < n; i++) {
                const j = Math.floor(Math.random() * n);
                [res[i], res[j]] = [res[j], res[i]];
            }
            return res;
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * var obj = new Solution(nums)
     * var param_1 = obj.reset()
     * var param_2 = obj.shuffle()
     */
    
    
  • /**
     * @param {number[]} nums
     */
    const Solution = function (nums) {
        this.nums = nums || [];
    };
    
    /**
     * Resets the array to its original configuration and return it.
     * @return {number[]}
     */
    Solution.prototype.reset = function () {
        return this.nums;
    };
    
    /**
     * Returns a random shuffling of the array.
     * @return {number[]}
     */
    Solution.prototype.shuffle = function () {
        let a = this.nums.slice();
        for (let i = 0; i < a.length; i++) {
            let rand = Math.floor(Math.random() * (a.length - i)) + i;
            let tmp = a[i];
            a[i] = a[rand];
            a[rand] = tmp;
        }
        return a;
    };
    
    /**
     * Your Solution object will be instantiated and called as such:
     * var obj = Object.create(Solution).createNew(nums)
     * var param_1 = obj.reset()
     * var param_2 = obj.shuffle()
     */
    
    
  • use rand::Rng;
    struct Solution {
        nums: Vec<i32>,
    }
    
    /**
     * `&self` means the method takes an immutable reference.
     * If you need a mutable reference, change it to `&mut self` instead.
     */
    impl Solution {
        fn new(nums: Vec<i32>) -> Self {
            Self { nums }
        }
    
        fn reset(&self) -> Vec<i32> {
            self.nums.clone()
        }
    
        fn shuffle(&mut self) -> Vec<i32> {
            let n = self.nums.len();
            let mut res = self.nums.clone();
            for i in 0..n {
                let j = rand::thread_rng().gen_range(0, n);
                res.swap(i, j);
            }
            res
        }
    }
    
    /**
     * Your Solution object will be instantiated and called as such:
     * let obj = Solution::new(nums);
     * let ret_1: Vec<i32> = obj.reset();
     * let ret_2: Vec<i32> = obj.shuffle();
     */
    

All Problems

All Solutions