C++ solution with Fisher Yates algorithm


  • 12

    Use Fisher Yates algorithm to randomize. Keep an extra idx array to store the original index of each element, so that we can correctly reset each element to its original position. Also note that "srand(time(NULL))" must be placed in the constructor, not the shuffle() function.

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

  • -2
    H
    This post is deleted!

  • 1

    @hunterzhao_ Can you elaborate on what you've said? Thanks.


  • -1
    H
    This post is deleted!

  • 0

    why not just

    arr=nums;
    idx=nums;
    

    ?


  • 0

    @Dragon.PW Yeah I think that will also work.


  • 0
    5

    I think num[i] appear at index j is not 1/n probability (if j>i,the probability is 1/(1+j)).


  • 3
    S

    @fittaoee you can do it much concise

    class Solution {
        private:
        vector<int> vi, vo;
        public:
        Solution(vector<int> nums) {
            vi = vo = nums;
        }
    
        vector<int> reset() {
            return vi = vo;
        }
    
        vector<int> shuffle() {
            int i = 0, j = 0;
            for (i = vi.size() - 1; i > 0; --i) {
                j = rand() % (i + 1);
                swap(vi[i], vi[j]);
            }
            return vi;
        }
    };

  • 0
    K

    @hunterzhao_ Yes, @fittaoee could use copy assignment operator = which could make the code precise. That's why you can't say such words. This forum is not for a person like you!


  • 0
    W

    This is my AC solution. But I don't know whether using swap(A[i], A[rand() % n]) instead of swap(A[i], A[rand() % (i + 1)]) is right?
    @StefanPochmann Can you help me?

    class Solution {
    public:
        Solution(const vector<int> &nums) : A(nums), original(nums) {
            srand(time(nullptr));
        }
        
        /** Resets the array to its original configuration and return it. */
        const vector<int>& reset() { return original; }
        
        /** Returns a random shuffling of the array. */
        const vector<int>& shuffle() {
            auto n = A.size();
            for (int i = 0; i < n; ++i)
                swap(A[i], A[rand() % n]);
            return A;
        }
        
    private:
        vector<int> A;
        vector<int> original;
    };
    

Log in to reply
 

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