Shuffle An Array Problem


Description

LeetCode Problem 384.

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:

1
2
3
4
5
6
7
8
9
10
11
12
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 <= 200
  • -10^6 <= nums[i] <= 10^6
  • All the elements of nums are unique.
  • At most 5 * 10^4 calls in total will be made to reset and shuffle.


Sample C++ Code

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
35
class Solution {
public:
    vector<int> orig;
    vector<int> tmp;
    
    Solution(vector<int>& nums) {
        orig = nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return orig;
    }
    
    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        int n = orig.size();
        tmp = orig;
        vector<int> ans;
        while (n > 0) {
            int r = rand() % n;
            ans.push_back(tmp[r]);
            tmp[r] = tmp[n-1];
            n --;
        }
        return ans;
    }
};

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




Related Posts

1-Bit And 2-Bit Characters Problem

LeetCode 717. We have two special characters, the first character...

Teemo Attacking Problem

LeetCode 495. Our hero Teemo is attacking an enemy Ashe...

Range Addition II Problem

LeetCode 598. You are given an m x n matrix...

Max Consecutive Ones Problem

LeetCode 485. Given a binary array nums, return the maximum...

132 Pattern Problem

LeetCode 456. Given an arrayof n integers nums, a 132...

Summary Ranges Problem

LeetCode 228. You are given a sorted unique integer array...