C++ solution, seems extremely slow, any better ideas?


  • 0
    W
    class Solution {
        vector<int> orig;
        
    public:
        Solution(vector<int> nums) {
            for(auto &it: nums) this->orig.push_back(it);
        }
        
        /** Resets the array to its original configuration and return it. */
        vector<int> reset() {
            return this->orig;
        }
        
        /** Returns a random shuffling of the array. */
        vector<int> shuffle() {
            vector<int> newArr(this->orig.begin(), this->orig.end());
            for(int len = newArr.size(); len > 0; --len) {
                int idx = rand() % len;
                swap(newArr[idx], newArr[len-1]);
            }
            return newArr;
        }
    };
    
    /**
     * 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();
     */
    
    

  • 0

    @wl5888
    I tried several other solutions in C++, the time cost is just about 360ms so far. B.T.W. perhaps your solution is little bit messy.

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

  • 1

    @LHearen said in C++ solution, seems extremely slow, any better ideas?:

    B.T.W. perhaps your solution is little bit messy.

    But at least it's not wrong like yours :-P


  • 2
    F

    @LHearen
    Hi.

    Take [1,2,3] as an example.
    In your solution, there are 27 statuses and in fact there are 6 permutations only. 27 is not divisible for 6, so the probabilities are not the same for sure.


  • 0

    @FlyChicken Your contradiction analysis is quite right, sorry about my carelessness. The solution in my last post is what I always use to avoid the worst case in quickSort.
    @StefanPochmann Thank you, man. You are not that mean as usual, hahah. Good point!

    class Solution {
    private:
        vector<int> oldArr;
    public:
        Solution(vector<int> nums) {
            oldArr = nums;
        }
        
        /** Resets the array to its original configuration and return it. */
        vector<int> reset() {
            return oldArr;
        }
        
        /** Returns a random shuffling of the array. */
        vector<int> shuffle() {
           vector<int> newArr = oldArr;
           for(int size = newArr.size(); size; --size)
                swap(newArr[size-1], newArr[rand()%size]);
           return newArr;
        }
    };
    

Log in to reply
 

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