Knuth shuffle O(n)


  • 0
    K

    Here we run the well know Knuth shuffle algorithm to generate a random permutation.

    class Solution {
    private:
        vector<int> orig;
        
    public:
        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() {
            vector<int> randShuf( orig );
            for(int i = orig.size()-1; i > 0; --i){
                int j = rand() % (i+1);
                std::swap(randShuf[i], randShuf[j]);
            }
            
            return randShuf;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.