O(n) space, O(n) time (for shuffle) cpp solution


  • 0
    J

    Bet anyone could think of such algorithm. Hope someone can give a more elegant and effective algorithm.

    The idea is simple, just using two vectors to store the numbers, one is original, one is to be shuffled.
    The shuffle algorithm is the Knuth Shuffle:

    1. Randomly choose a value in the vector from 0 ... size. (size is initialized of vector.size() - 1)
    2. Swap the value with the size-th last value of the vector
    3. Reduce the size by 1.
    4. Go to 1 while size > 0

    The code is here:

    class Solution {
        vector<int> original;
        vector<int> shuf;
    public:
        Solution(vector<int> nums) {
            original = nums;
            shuf = nums;
        }
        
        /** Resets the array to its original configuration and return it. */
        vector<int> reset() {
            return original;
        }
        
        /** Returns a random shuffling of the array. */
        vector<int> shuffle() {
            if(shuf.empty())
                return shuf;
            for(int i = shuf.size(); i > 0; --i)
                swap(shuf[rand() % i], shuf[i - 1]);
            return shuf;
        }
    };
    
    /**
     * 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();
     */
    

  • 1

    @jtimberlakers said in O(n) space, O(n) time (for shuffle) cpp solution:

    vector<int> shuffle() {
        if(shuf.empty())
            return shuf;
        for(int i = shuf.size(); i > 0; --i)
            swap(shuf[rand() % i], shuf[shuf.size() - 1]);
        return shuf;
    }
    

    That's wrong. For example, shuffling [1, 2, 3] ends up as [3, 2, 1] twice as likely as it should, and [3, 1, 2] is impossible.


  • 0
    J

    @StefanPochmann Oh, yes. Just edit the code to replace the shuf[shuf.size()-1] to shuf[i - 1]. That'll work.


  • 0
    This post is deleted!

Log in to reply
 

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