C++ Solution with O(n) time complexity for both reset and shuffle operation


  • 0
    Y

    For the shuffle operation, the first move is 1/n, the second one become 1/(n-1) ... the last one is 1. So the probability of new sequence generated is 1/n*1/(n -1)*1/(n-2)...1 = 1/(n!).

    class Solution {
    public:
        Solution(vector<int> nums) {
            srand (time(NULL));
            arr.resize(nums.size());
            orgarr.resize(nums.size());
            for(int i = 0; i < nums.size(); ++ i)
                orgarr[i] = arr[i] = nums[i];
        }
        
        /** Resets the array to its original configuration and return it. */
        vector<int> reset() {
            if(arr.size() == 0)
                return arr;
            for(int i = 0; i < arr.size(); ++ i)
                arr[i] = orgarr[i];
            return arr;
        }
        
        /** Returns a random shuffling of the array. */
        vector<int> shuffle() {
            if(arr.size() == 0)
                return arr;
            for(int i = 0; i < arr.size() - 1; ++ i)
                swap(arr[i], arr[rand()%(arr.size() - i) + i]);
            return arr;
        }
    private:
        vector<int> arr, orgarr;
    };
    
    

Log in to reply
 

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