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.
Solutions
Solution 1
1 2 3 4 5 6 7 8 91011121314151617181920
classSolution:def__init__(self,nums:List[int]):self.nums=numsself.original=nums.copy()defreset(self)->List[int]:self.nums=self.original.copy()returnself.numsdefshuffle(self)->List[int]:foriinrange(len(self.nums)):j=random.randrange(i,len(self.nums))self.nums[i],self.nums[j]=self.nums[j],self.nums[i]returnself.nums# Your Solution object will be instantiated and called as such:# obj = Solution(nums)# param_1 = obj.reset()# param_2 = obj.shuffle()
classSolution{privateint[]nums;privateint[]original;privateRandomrand;publicSolution(int[]nums){this.nums=nums;this.original=Arrays.copyOf(nums,nums.length);this.rand=newRandom();}publicint[]reset(){nums=Arrays.copyOf(original,original.length);returnnums;}publicint[]shuffle(){for(inti=0;i<nums.length;++i){swap(i,i+rand.nextInt(nums.length-i));}returnnums;}privatevoidswap(inti,intj){intt=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(); */
classSolution{public:vector<int>nums;vector<int>original;Solution(vector<int>&nums){this->nums=nums;this->original.resize(nums.size());copy(nums.begin(),nums.end(),original.begin());}vector<int>reset(){copy(original.begin(),original.end(),nums.begin());returnnums;}vector<int>shuffle(){for(inti=0;i<nums.size();++i){intj=i+rand()%(nums.size()-i);swap(nums[i],nums[j]);}returnnums;}};/** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(nums); * vector<int> param_1 = obj->reset(); * vector<int> param_2 = obj->shuffle(); */
typeSolutionstruct{nums,original[]int}funcConstructor(nums[]int)Solution{returnSolution{nums,append([]int(nil),nums...)}}func(this*Solution)Reset()[]int{copy(this.nums,this.original)returnthis.nums}func(this*Solution)Shuffle()[]int{n:=len(this.nums)fori:=rangethis.nums{j:=i+rand.Intn(n-i)this.nums[i],this.nums[j]=this.nums[j],this.nums[i]}returnthis.nums}/** * Your Solution object will be instantiated and called as such: * obj := Constructor(nums); * param_1 := obj.Reset(); * param_2 := obj.Shuffle(); */
classSolution{privatenums:number[];constructor(nums:number[]){this.nums=nums;}reset():number[]{returnthis.nums;}shuffle():number[]{constn=this.nums.length;constres=[...this.nums];for(leti=0;i<n;i++){constj=Math.floor(Math.random()*n);[res[i],res[j]]=[res[j],res[i]];}returnres;}}/** * 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() */
userand::Rng;structSolution{nums:Vec<i32>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implSolution{fnnew(nums:Vec<i32>)->Self{Self{nums}}fnreset(&self)->Vec<i32>{self.nums.clone()}fnshuffle(&mutself)->Vec<i32>{letn=self.nums.len();letmutres=self.nums.clone();foriin0..n{letj=rand::thread_rng().gen_range(0,n);res.swap(i,j);}res}}
/** * @param {number[]} nums */constSolution=function(nums){this.nums=nums||[];};/** * Resets the array to its original configuration and return it. * @return {number[]} */Solution.prototype.reset=function(){returnthis.nums;};/** * Returns a random shuffling of the array. * @return {number[]} */Solution.prototype.shuffle=function(){leta=this.nums.slice();for(leti=0;i<a.length;i++){letrand=Math.floor(Math.random()*(a.length-i))+i;lettmp=a[i];a[i]=a[rand];a[rand]=tmp;}returna;};/** * 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() */