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 <vector>
2#include <algorithm>
3#include <ctime>
4#include <cstdlib>
5
6class Solution {
7private:
8 std::vector<int> original;
9 std::vector<int> array;
10public:
11 Solution(std::vector<int>& nums) : original(nums), array(nums) {
12 std::srand(std::time(0));
13 }
14 std::vector<int> reset() {
15 array = original;
16 return array;
17 }
18 std::vector<int> shuffle() {
19 for (int i = array.size() - 1; i > 0; --i) {
20 int j = std::rand() % (i + 1);
21 std::swap(array[i], array[j]);
22 }
23 return array;
24 }
25};In C++, we use the 'vector' class to store the array. We initialize the original and array vectors with the given nums. The shuffle function uses the Fisher-Yates algorithm to rearrange the elements randomly.
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.
1from random import randint
2
3class Solution:
In this Python solution, we recursively generate a permutation by swapping the current element with any element after it. This ensures that all permutations are equally probable, though it's less efficient for large arrays compared to Fisher-Yates.