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 arraynums
.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 toreset
andshuffle
.
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(); */