Sponsored
The Fisher-Yates shuffle algorithm, also known as the Knuth shuffle, is an efficient algorithm for generating a random permutation of a finite sequence. The algorithm works by iterating backward through the array and swapping each element with a randomly selected element from the portion of the array that has not been shuffled yet.
Time Complexity: O(n) for both reset and shuffle functions.
Space Complexity: O(n) for maintaining a copy of the original array.
1#include <stdio.h>
2#include <stdlib.h>
3#include <time.h>
4
5typedef struct Solution {
6 int* original;
7 int* array;
8 int size;
9} Solution;
10
11Solution* solutionCreate(int* nums, int size) {
12 Solution* obj = (Solution*)malloc(sizeof(Solution));
13 obj->original = (int*)malloc(size * sizeof(int));
14 obj->array = (int*)malloc(size * sizeof(int));
15 obj->size = size;
16 for (int i = 0; i < size; ++i) {
17 obj->original[i] = nums[i];
18 obj->array[i] = nums[i];
19 }
20 srand(time(NULL));
21 return obj;
22}
23
24int* solutionReset(Solution* obj, int* ret_size) {
25 for (int i = 0; i < obj->size; ++i) {
26 obj->array[i] = obj->original[i];
27 }
28 *ret_size = obj->size;
29 return obj->array;
30}
31
32int* solutionShuffle(Solution* obj, int* ret_size) {
33 for (int i = obj->size - 1; i > 0; --i) {
34 int j = rand() % (i + 1);
35 int temp = obj->array[i];
36 obj->array[i] = obj->array[j];
37 obj->array[j] = temp;
38 }
39 *ret_size = obj->size;
40 return obj->array;
41}
42
43void solutionFree(Solution* obj) {
44 free(obj->original);
45 free(obj->array);
46 free(obj);
47}In the C implementation, we first allocate memory for the 'Solution' structure. We perform a deep copy of the input array for both the 'original' and 'array' members of the structure. The 'reset' function restores the 'array' to its original configuration, while the 'shuffle' function uses the Fisher-Yates algorithm to shuffle the 'array'. We clean up memory in 'solutionFree'.
This approach involves generating a permutation recursively by picking an element and placing it at different positions. This is less efficient than the Fisher-Yates method and not suitable for large arrays.
Time Complexity: O(n!) because it attempts every permutation recursively.
Space Complexity: O(n) for maintaining the array copy.
1class Solution {
2 constructor(nums) {
In JavaScript, this solution uses recursion to generate permutations, not fully efficient nor strictly generating permutations but a form of randomized shuffle which is recursive, ensuring all elements are possibly swapped.