384. Shuffle an Array
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
- − 1 0 6 < = n u m s [ i ] < = 1 0 6 -10^6 <= nums[i] <= 10^6 −106<=nums[i]<=106
- All the elements of nums are unique.
- At most 1 0 4 10^4 104 calls in total will be made to reset and shuffle.
From: LeetCode
Link: 384. Shuffle an Array
Solution:
Ideas:
-
Struct Definition: The Solution struct contains pointers to the original and shuffled arrays, along with the size of the array.
-
Constructor (solutionCreate): Initializes the struct, copying the original array and allocating memory for both the original and shuffled arrays.
-
Reset Method (solutionReset): Resets the shuffled array back to the original configuration and returns it.
-
Shuffle Method (solutionShuffle): Implements the Fisher-Yates shuffle algorithm to randomly shuffle the elements of the array.
-
Destructor (solutionFree): Frees the allocated memory to prevent memory leaks.
Code:
typedef struct {int* original;int* shuffled;int size;
} Solution;Solution* solutionCreate(int* nums, int numsSize) {Solution* obj = (Solution*)malloc(sizeof(Solution));obj->original = (int*)malloc(numsSize * sizeof(int));obj->shuffled = (int*)malloc(numsSize * sizeof(int));obj->size = numsSize;memcpy(obj->original, nums, numsSize * sizeof(int));memcpy(obj->shuffled, nums, numsSize * sizeof(int));// Initialize random number generatorsrand(time(NULL));return obj;
}int* solutionReset(Solution* obj, int* retSize) {*retSize = obj->size;memcpy(obj->shuffled, obj->original, obj->size * sizeof(int));return obj->shuffled;
}int* solutionShuffle(Solution* obj, int* retSize) {*retSize = obj->size;// Perform Fisher-Yates shufflefor (int i = obj->size - 1; i > 0; i--) {int j = rand() % (i + 1); // Random index from 0 to i// Swap shuffled[i] with shuffled[j]int temp = obj->shuffled[i];obj->shuffled[i] = obj->shuffled[j];obj->shuffled[j] = temp;}return obj->shuffled;
}void solutionFree(Solution* obj) {free(obj->original);free(obj->shuffled);free(obj);
}/*** Your Solution struct will be instantiated and called as such:* Solution* obj = solutionCreate(nums, numsSize);* int* param_1 = solutionReset(obj, retSize);* int* param_2 = solutionShuffle(obj, retSize);* solutionFree(obj);
*/